uva 11627 Slalom (二分法)

uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2674

　　一道比较明显的二分题，主要是在二分的判断上耗费了一点时间。

代码如下：

View Code

 1 typedef pair<int, int> PII;
 2 typedef vector<int> VI;
 3 typedef vector<PII> VPII;
 4 
 5 #define REP(i, n) for (int i = 0; i < (n); i++)
 6 #define REP_1(i, n) for (int i = 1; i <= (n); i++)
 7 
 8 VPII gate;
 9 VI ski;
10 double w;
11 int v, n;
12 
13 bool cmp(PII a, PII b) {
14     return a > b;
15 }
16 
17 void input() {
18     int l, h;
19     gate.clear();
20     scanf("%lf%d%d", &w, &v, &n);
21     REP(i, n) {
22         scanf("%d%d", &l, &h);
23         gate.PB(MPR(h, l));
24     }
25     gate.PB(MPR(0, 0));
26     sort(ALL(gate), cmp);
27 //    REP(i, SZ(gate)) cout << gate[i].FI << ends << gate[i].SE << endl;
28     ski.clear();
29     scanf("%d", &n);
30     REP(i, n) {
31         scanf("%d", &h);
32         ski.PB(h);
33     }
34     ski.PB(inf);
35     ski.PB(-inf);
36     sort(ALL(ski));
37 }
38 
39 bool test(int x) {
40     double L = -finf, R = finf;
41     REP(i, SZ(gate) - 1) {
42         double l = gate[i].SE, r = gate[i].SE + w, d = ((double) gate[i].FI - gate[i + 1].FI) * v / x;
43 //        cout << L << ends << R << ends << l << ends << r << ends << d << endl;
44         if (r < L || R < l) return false;
45         L = max(L, l), R = min(R, r);
46         L -= d, R += d;
47     }
48     return true;
49 }
50 
51 int bs() {
52     int h = 1, t = 1e7, mk = 0, m;
53     while (h <= t) {
54         m = (h + t) >> 1;
55         if (test(m)) mk = m, h = m + 1;
56         else t = m - 1;
57     }
58     return mk;
59 }
60 
61 int main() {
62 //    freopen("in", "r", stdin);
63     int T;
64     scanf("%d", &T);
65     while (T--) {
66         input();
67         int ans = ski[upper_bound(ALL(ski), bs()) - ski.begin() - 1];
68 //        printf("%d %d\n", ans, bs());
69         if (ans == -inf || ans == inf) puts("IMPOSSIBLE");
70         else printf("%d\n", ans);
71     }
72     return 0;
73 }

——written by Lyon