首页 > 代码库 > UVA11627-Slalom
UVA11627-Slalom
题目链接
题意:有n个宽为w的旗门,第i个旗门左端的坐标为(xi, yi),对于所有1 <= i < n满足yi < y(i+1)。你有s双滑雪板,第j双的速度为sj(垂直向下的速度)。你的水平速度不能超过v(任意变速)。起点和终点的坐标任意选择,求用时最少可以通过所有旗门的滑雪板。
思路:当垂直速度越小时,到达下一个旗门的概率就越大。所以先将滑雪板的速度从小到大排序。其实一个旗门到下一个旗门是有一个区间的,所以只要下一个旗门与这个区间有交集,就代表能从上一个抵达下一个,我们就可以根据这个做法加上二分法查找能通过所有旗门的最大速度。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1000005; struct gate{ double x, y; }g[MAXN]; int w, v, n, s; int sv[MAXN]; int judge(int mid) { double ss = sv[mid]; double l = g[n - 1].x; double r = g[n - 1].x + w; for (int i = n - 2; i >= 0; i--) { l -= (v * (g[i + 1].y - g[i].y) / ss); r += (v * (g[i + 1].y - g[i].y) / ss); if (l < g[i].x) l = g[i].x; if (r > g[i].x + w) r = g[i].x + w; if (r < l) { return false; } } return true; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%d%d", &w, &v, &n); for (int i = 0; i < n; i++) scanf("%lf %lf", &g[i].x, &g[i].y); scanf("%d", &s); for (int i = 0; i < s; i++) scanf("%d", &sv[i]); sort(sv, sv + s); int L = -1, R = s, mid; while (L < R - 1) { mid = L + (R - L) / 2; if (judge(mid)) L = mid; else R = mid; } if (L == -1) printf("IMPOSSIBLE\n"); else printf("%d\n", sv[L]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。