poj3484 Showstopper 二分

题目地址

二分用的很是巧妙！关键是抽象出问题本质。

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstring>
 4 const int maxn = 100000;
 5 #define ull unsigned long long
 6 ull X[maxn], Y[maxn], Z[maxn], C[maxn];
 7 ull N;
 8 ull judge(const ull &mid) {
 9     ull sum = 0;
10     for (int i = 0; i < N; i++) {
11         if (mid >= Y[i]) {
12             sum += C[i];
13         } else if (mid >= X[i]) {
14             sum += ((mid-X[i])/Z[i]+1);
15         }
16     }
17     return sum;
18 }
19 char buf[1024];
20 bool input() {
21     int f = 0;
22     N = 0;
23     while ((f = ((gets(buf) != NULL))) && strlen(buf) > 2) {
24         sscanf(buf, "%llu %llu %llu", &X[N], &Y[N], &Z[N]);
25         N++;
26     }
27     return f || N;
28 }
29 int main(void) {
30     for (;input();) {
31         if (!N) {
32             continue;
33         }
34         ull last = 0;
35         for (int i = 0; i < N; i++) {
36             C[i] = (Y[i] - X[i])/Z[i] + 1;
37             last ^= C[i];
38         }
39         if (!(last & 1)) {
40             printf("no corruption\n");
41         } else {
42             ull l = 0, u = 0xffffffff;
43             for (;(u-l)>0;) {
44                 ull mid = (u+l) >> 1;
45                 if (judge(mid)&1) {
46                     u = mid;
47                 } else {
48                     l = mid +1;
49                 }
50             }
51             printf("%llu %llu\n", l, judge(l)-judge(l-1));
52         }
53     }
54     return 0;
55 }

View Code