【ZOJ月赛】【二分查找】【A.Edward's Cola Plan】

【题目来源】http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4929

【个人体会】这个题目是我在4小时50多分钟最后AC的，因为我一看这个题目时限是3S就有点心虚，怕为了搞这个题目而忽略了“可能”存在的水题，最后连这个题目也没搞出来。不过后来看到这个题目过的人数就发现了原来这个题目才是水题。。。

【题目大意】唧唧歪歪半天，意思很简单。就是对于每个朋友，在Pi和Qi-M中选一个大的，然后求和。接着，给出T组询问，每次M的值都在变化，要求每组询问的和。

【题目解析】根据Qi-Pi的差值进行排序，对于每组M，求出它在排序后的数组中的位置(二分查找)，然后对于这个位置以前的所有人都选Pi，对于这个位置以后的所有人都选Qi-M。另外，预处理出Pi和Qi的前缀和。

【代码如下】

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 struct Cola
 7 {
 8     int p, q;
 9 }A[100005];
10 
11 int N, T, Sumq[100005], Sump[100005];
12 
13 bool Cmp(const Cola &a, const Cola &b)
14 {
15     return ((a.q - a.p) < (b.q - b.p));
16 }
17 
18 void Solve()
19 {
20     sort(A + 1, A + 1 + N, Cmp);
21     for (int i = 1; i <= N; i ++)
22     {
23         Sump[i] = Sump[i - 1] + A[i].p;
24         Sumq[i] = Sumq[i - 1] + A[i].q;
25     }
26     for (int i = 1, M; i <= T; ++i)
27     {
28         scanf("%d", &M);
29         int l = 1, r = N + 1, ans = -1;
30         while (l <= r)
31         {
32             int m = (l + r) / 2;
33             if (A[m].q - A[m].p < M) l = m + 1;
34             else
35             {
36                 ans = m; r = m - 1;
37             }
38         }
39         if (ans == -1) printf("%d\n", Sump[N]);
40         else printf("%d\n", Sump[ans - 1] + Sumq[N] - Sumq[ans - 1] - M * (N - ans + 1));
41     }
42 }
43 
44 void Init()
45 {
46     for (int i = 1; i <= N; ++i) scanf("%d%d", &A[i].p, &A[i].q);
47 }
48 
49 int main()
50 {
51     while (scanf("%d%d", &N, &T) != EOF)
52     {
53         Init();
54         Solve();
55     }
56     return 0;
57 }