本文共 1250 字，大约阅读时间需要 4 分钟。
二分
#include #include #include #include #include #include #include #include #include #include #include #include #include #define maxn 100010#define INF 0x7fffffff#define inf 10000000#define MOD 1000000007#define ull unsigned long long#define ll long longusing namespace std;struct node{ int x, y;};node houge[maxn];int n, v, w, s[maxn*10], m;bool ok(int mid){ double st = houge[0].x, en = houge[0].x+w; for(int i = 1; i < n; ++ i) { double len = (double)(houge[i].y-houge[i-1].y)/s[mid]*v; st -= len; en += len; st = max(st, (double)houge[i].x); en = min(en, (double)houge[i].x+w); if(st > en+1e-6) return false; } return true;}int solve(){ int ans = -1; int rig = 0, le = m; while(rig < le) { int mid = rig + (le-rig)/2; if(ok(mid)) { rig = mid+1; ans = mid; } else le = mid; } return ans;}int main(){ int t; scanf("%d", &t); while(t --) { scanf("%d%d%d", &w, &v, &n); for(int i = 0; i < n; ++ i) scanf("%d%d", &houge[i].x, &houge[i].y);; scanf("%d", &m); for(int i = 0; i < m; ++ i) scanf("%d", &s[i]); sort(s, s+m); int ans = solve(); if(ans != -1) printf("%d\n", s[ans]); else puts("IMPOSSIBLE"); } return 0;}
转载于:https://www.cnblogs.com/avema/p/3774177.html