题目链接

聪明的质检员

题目思路

二分+前缀和优化
#代码实现

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long 
const int Max=1e6;
ll n,m,s;
ll v[Max],w[Max],L[Max],R[Max],sum[Max],cnt[Max];
ll check(int x)
{
    ll res=0;
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=x)
        {
            sum[i]=sum[i-1]+v[i];
            cnt[i]=cnt[i-1]+1;
        }
        else
        {
            sum[i]=sum[i-1];
            cnt[i]=cnt[i-1];
        }
    }
    for(int i=1;i<=m;i++)
    {
        res+=((cnt[R[i]]-cnt[L[i]-1])*(sum[R[i]]-sum[L[i]-1]));
    }
    return res;
}
int main()
{
    IOS;
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for(int i=1;i<=m;i++)
        cin>>L[i]>>R[i];
    ll l=1,r=1e13;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid)>=s)
            l=mid+1;
        else r=mid-1;
    }
    cout<<min(abs(check(l)-s),abs(check(l-1)-s));
    return 0;
}