题解 P1314 【聪明的质监员】

· · 题解

//这道题要找一个参数 这二分妥妥的。。。不然就t成翔吧。。。O(∩_∩)O~

//每一次二分 都要预处理 cnt[i]表示 对于当前二分到的参数 前 i 个有多少符合要求

//sum[i]表示 对于当前二分的参数 前 i 个符合要求的点的点权和

//然后就按着题意来吧
//找到 使结果比标准值小的  最靠近的那一个 参数  再考虑这个参数+1  就可以了
//同样  求出当前参数  和参数+1 时的 |s-y|  再输出小的  就好了
//时间复杂度  nmlogn
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#define MAXN 200000+10  
using namespace std;  
long long  an,s,sum[MAXN];  
int n,m,cnt[MAXN],v[MAXN],w[MAXN],lef[MAXN],rig[MAXN],l,r;  
void readdata()  
{  
    cin>>n>>m>>s;
    for(int i = 1 ; i <= n ; i++ )  
        {  
            cin>>w[i]>>v[i];
            r = max(r,w[i]);  
        }  
    for(int i = 1;i <= m ;i++)  
        cin>>lef[i]>>rig[i];    
}  
bool check(int res)  
{     
    an=0;  
    for(int i = 1;i <= n;i++)  
    {  
        if(w[i] >= res)  
            {  
                cnt[i] = cnt[i-1] + 1;  
                sum[i] = sum[i-1] + v[i];  
            }  
        else  
            {  
                cnt[i] = cnt[i-1];  
                sum[i] = sum[i-1];  
            }         
    }  
    for(int i = 1;i <= m ;i++)  
        an += (sum[rig[i]] - sum[lef[i] - 1]) * (cnt[rig[i]] - cnt[lef[i] - 1]);  
    if (an <= s)  
    return 1;  
    else return 0;  
}  
void erfen()  
{     
    l=0;  
    r++;  
    while(l + 1< r)  
        {  
            int mid = (l+r) / 2;  
            if (check(mid))  
            {  
                if(an == s)  
                    {  
                        cout<<endl;
                        exit(0);  
                    }  
                r = mid ;           }  
            else  
            {  
                l = mid ;  
            }  
        }  
}  
int main()  
{  
    readdata();  
    erfen();  
    check(min(l,r));  
    long long  ans=an;  
    ans = s > ans ? s - ans : ans - s;  
    check(max(l,r));  
    an = an > s ? an - s : s - an;  
    if  (an>ans)  
    cout<<ans;
    else cout<<an; 
}