Output Specification
Output one line for each test case. If it is impossible to complete the race with any pair of skis, print the line IMPOSSIBLE. Otherwise, print the vertical speed s j of the pair of skis that allows you to get through the race course in the shortest time.Output for Sample Input
2 IMPOSSIBLE题意：给定n个门和门的长度，n双滑雪板，求最大能通过所有门的滑雪板的速度。
思路：二分答案，然后去判断，判断的时候每次只要维护一个区间就可以了。
代码：
#include#include #include using namespace std; const int N = 100005; int T, n, S, s[N * 10]; double w, v; struct Sk { double s, e, y; } sk[N]; void init() { scanf("%lf%lf%d", &w, &v, &n); for (int i = 0; i < n; i ++) { scanf("%lf%lf", &sk[i].s, &sk[i].y); sk[i].e = sk[i].s + w; } scanf("%d", &S); for (int i = 0; i < S; i ++) scanf("%d", &s[i]); sort(s, s + S); } bool judge(int sv) { double s = sk[n - 1].s, e = sk[n - 1].e; for (int i = n - 1; i > 0; i --) { double time = (sk[i].y - sk[i - 1].y) / sv; s = max(s - time * v, sk[i - 1].s); e = min(e + time * v, sk[i - 1].e); if (s > sk[i - 1].e || e < sk[i - 1].s || s > e) return false; } return true; } void solve() { if (!judge(s[0])) { printf("IMPOSSIBLE\n"); return; } int l = 0, r = S - 1; while (l < r) { int mid = (l + r)>>1; if (judge(s[mid])) l = mid + 1; else r = mid; } if (!judge(s[l])) l--; printf("%d\n", s[l]); } int main() { scanf("%d", &T); while (T--) { init(); solve(); } return 0; }