题解 P1314 【聪明的质监员】

· · 题解

二分

思路：

这道题思路还是蛮好想的，一开始想的是暴力枚举w，然后再仔细一看，w增长时，y肯定减小，那么思路出来了： 二分

但是在时二分时，分得是左右端点lr，做错了

求出w的上下界，然后二分

只二分是肯定不行的因为这是道蓝题呀我们在求出对应的yi时，用了n^{2}的时间复杂度，如何优化？要用到 前缀和

简单介绍一下，前缀和字面意思，就是前面一坨的和，我们用数组p表示，当我们需要求出区间[l , r]时，只需要将p[r]-p[l-1] ，证明很简单，推一下就行

注意事项：

  1. 开long long！！！

  2. 把最后的答案ans开大一点

  3. 这是一个单调递减的函数

  4. 左端点l要往左移1个（要判断l，所以从l-1开始），右端点r往右移两个（要判断w很大的情况，使y=0）

细节都在代码里了

#include <bits/stdc++.h>
using namespace std;
long long n , m , lef = 999999 , righ = 0 , S , anses , ans = 99999999999 , f;
long long l[200010] , r[200010] , w[200010] , v[200010] , p1[200010] , p2[200010];
long long work(long long ww){
    f = 0;
    memset(p1 , 0 , sizeof(p1)); //清空数组 
    memset(p2 , 0 , sizeof(p2));
    for(int i = 1; i <= n; i++){
        if(w[i] >= ww){
            p1[i] = p1[i - 1] + v[i];
            p2[i] = p2[i - 1] + 1;
        }else{
            p1[i] = p1[i - 1]; //不加进去的话就跟上次一样 
            p2[i] = p2[i - 1];
        }
    }
    for(int i = 1; i <= m; i++) f += (p1[r[i]] - p1[l[i] - 1]) * (p2[r[i]] - p2[l[i] - 1]); //计算 
    return f;
}
int main(){
    cin >> n >> m >> S;
    for(long long i = 1; i <= n; i++) cin >> w[i] >> v[i] , righ = max(righ , w[i]) , lef = min(lef , w[i]);
    for(long long i = 1; i <= m ;i++) cin >> l[i] >> r[i];
    //cout << endl;
    righ += 2;
    lef--;
    while(lef <= righ){
        long long mid = (lef + righ) / 2;
        anses = work(mid);
        if(anses >= S) lef = mid + 1;
        else righ = mid - 1;
        if(ans > abs(anses - S)) ans = abs(anses - S); //求更优值 
    }
    cout << ans;
    return 0;
}