题解 P1314 【聪明的质监员】

· · 题解

** woc 看到提高+吓我一跳= =

我想说这道题主要是在考语文！！！！

然后是二分W的值和前缀和优化（别的二分有一种优化是对有序数组二分下标，但是这里不适用）

主要坑点在于：S可以达到10^12 ，所以一是要防止数组爆掉（变量也是一样），二是函数的返回类型，比如check（或者还要做死写个优读，像我这样的）返回值为long long，三是最小值最大值要够！！不要赋成10^10，这个最值对于其中45分的数据是不够大的

目测至少到10^12 [delete]我因为这三点起码WA了5次QAQ，唉[/delete]

其余的，注意是差的绝对值的最小值，假如对于当前M算出结果是ans,那么要取

abs(ans-S)的最小值，不要只取ans-S的最小值

**


//代码好像有点长= =我写的拙劣
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const long long maxn=200000+10;
const long long INF=(1<<30);
typedef long long ll;

ll n,m,S;                       //我实在不想过于纠结哪些要用long long 哪些是int 还有哪些计算乘积的时候要强制转换，所以直接全部long long 了
ll w[maxn],v[maxn];
ll sum[maxn],cnt[maxn];
ll l[maxn],r[maxn];

inline ll read()
{
    ll ret=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
    return ret;
}

ll mind=INF*1000;                    //最大值一定要够！！！
ll cal(ll k)
{
    ll ret=0;
    sum[0]=cnt[0]=0;
    for(int i=1;i<=n;i++)
      if(w[i]>=k)
        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++)
    {
        ret = ret+(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
        if(ret-S>S) return ret;
    }
    return ret;
}

inline ll max(const ll &a,const ll &b)
{
    if(a>b) return a;
    return b;
}

inline ll min(const ll &a,const ll &b)
{
    if(a>b) return b;
    return a;
}

int main()
{
    cin>>n>>m>>S;
    ll maxw=-INF,minw=INF;            //w最大值只有10^6  这样应该是够得
    for(int i=1;i<=n;i++)
    {
        w[i]=read();v[i]=read();
        maxw=max(maxw,w[i]);
        minw=min(minw,w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        l[i]=read();r[i]=read();
    }
    ll lt=minw,rt=maxw;
    while(lt<=rt)
    {
        ll mid=lt+(rt-lt)/2;
        ll tmp=cal(mid);
        if(tmp==S) 
        {
            mind=0;break;
        }
        else if(tmp>S) 
        {
            lt=mid+1;
            if(tmp-S<mind)
            {
                mind=tmp-S;
            }
        }
        else  rt=mid-1,mind=min(mind,S-tmp);
    }
    cout<<mind;
    return 0;
}