聪明的质检员 (二分)

题目地址：https://vijos.org/p/1740

分析

首先题面一定要看懂，看清（上次我就是没有看懂）。说白了，就是使W取一个最合适的值，使每一个所给区间内满足条件的矿石的数量乘上价值之和，最后计算总和使与S最近。

我们根据分值分布来分析算法：

1、30分算法：O（n^3），首先O（n）进行W值选取的枚举，然后O（n^2）判断+计算；

2、50分算法：O（n^2 log n）。根据每次选取W值我们易发现，所得的总值是一个单调函数，随W增大而减小，且一定存在零点。故为了求得最小值，我们需要得到零点位于那两个整数之间。这样用二分显然比枚举快。O（log n）的二分加上O（n^2）的判断+计算；

3、100分算法：200000的数据显然只能O（n log n）或者O（n）了，但是这道题O（n）很明显不现实。我们的任务在于，如何消去O（n^2）这么大的判断与计算？这里，可以采取前缀和优化——由于每次计算检验值之和的时候，W值固定，故可以用O（n）的时间扫描一遍，用s1[i]表示前i个矿石满足条件的个数；s2[i]表示前i个满足条件的矿石价值之和。故每次询问一个区间的时候，可以O（1）直接相减！这样，复杂度就降到了O（n log n）。（这其实是一个很简单的优化但是我想了很久，看来姿势不够）

4、（这个可以无视）70分算法：存在这个分数段就必然存在这种算法对吧。。。这一定是给那些用了前缀和却没有用二分的。。。虽然我觉得很不可思议。

还有一个很重要的数据范围——权值会爆INT。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 long long w[200002];
 8 long long v[200002];
 9 long long W;
10 long long L[200002];    
11 long long R[200002];
12 long long s1[200002];    // 记录个数 
13 long long s2[200002];    // 记录价值和 
14 long long n, m, S;
15 long long wmax;
16 
17 
18 long long cal(int x)
19 {
20     memset(s1, 0, sizeof(s1));
21     memset(s2, 0, sizeof(s2));
22     
23     for(int i = 1; i <= n; ++i)
24     {
25         if(w[i] >= x)
26         {
27             s1[i] = s1[i-1] + 1;    
28             s2[i] = s2[i-1] + v[i];
29         }
30         else
31         {
32             s1[i] = s1[i-1];
33             s2[i] = s2[i-1];
34         }
35     }
36     
37     long long ret = 0;
38     for(int i = 1; i <= m; ++i)
39     {
40         ret += ( s1[R[i]] - s1[L[i]-1] ) * ( s2[R[i]] - s2[L[i]-1] );　　// 前缀和代替枚举，优化复杂度
41     }
42     
43     return ret;
44     
45     
46 }
47 
48 int main()
49 {
50     while(scanf("%lld %lld %lld", &n, &m, &S) != EOF)
51     {
52         wmax = 0;
53         for(int i = 1; i <= n; ++i)
54         {
55             scanf("%lld %lld", &w[i], &v[i]);
56             if(wmax < w[i])
57                 wmax = w[i];
58         }
59         
60         for(int i = 1; i <= m; ++i)
61         {
62             scanf("%lld %lld", &L[i], &R[i]);
63         }
64         
65         long long ans = 20000000000000000;　　// 要比S大
66         long long left = 0, right = wmax;
67         while(left <= right)    // 此处一定要有等于号 
68         {
69             long long mid = (left+right)/2;
70             long long ret = cal(mid);
71             if(ret < S)
72             {
73                 right = mid - 1;
74                 if(ans > S - ret)
75                     ans = S - ret;
76             }
77             else
78             {
79                 left = mid + 1;
80                 if(ans > ret - S)
81                     ans = ret - S;
82             }
83         }    
84         
85         printf("%lld
", ans);    
86         
87     }
88     
89     return 0;
90 }