题解 P1314 【聪明的质监员】

licone · 2016-07-18 21:29:46 · 题解

二分题~

二分w的值，与所给标准值s对比，[注意这里与其他的二分不一样~] 如果大，就将右边标记j改为此时的w值-1；如果小，就将左边标记i改为w+1，保证区间每次都更贴近标准值。注意同时要更新答案tot值~

另外，如果每次都循环求值会超时，可以预处理出前缀和~

这道题的数据范围较大，答案用long long型~这道题里面哪些用long long型，哪些用int型要区分清楚~

具体的看代码~

#include<cstdio>
#include<cstring>
#define ll long long
int w[200006],n,m;
int x[200006],y[200006],a[200006];
ll k,tot=12425374554373ll,mx,mi=0xfffffff,s[200006],v[200006];  //long long型  
ll lmin(ll u,ll v)
{
    return u<v ? u:v;
}
int min(int u,int v)
{
    return u<v ? u:v;
}
int max(int u,int v)
{
    return u>v ? u:v;
}
ll doo(int u)
{
    ll ans=0;
    memset(a,0,sizeof(a));
    memset(s,0,sizeof(s));
    for(int i=1;i<=n;i++)  //预处理  
    {
        if(w[i]>=u) a[i]=a[i-1]+1,s[i]=s[i-1]+v[i];  //传说中的前缀和~
        else a[i]=a[i-1],s[i]=s[i-1];
    }
    for(int i=1;i<=m;i++) ans+=(a[y[i]]-a[x[i]-1])*(s[y[i]]-s[x[i]-1]);
    return ans;
}
int main()
{
    scanf("%d%d%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&v[i]);
        mx=max(w[i],mx);mi=min(w[i],mi);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    int i=mi,j=mx;
    while(i<=j)
    {
        int mid=(i+j)/2;
        ll zz=doo(mid);
        if(zz>k) 
        {
            i=mid+1;tot=lmin(tot,zz-k);  //这里i和j的顺序与一般的二分不同，要反过来  
        }
        else if(zz<k)
        {
            j=mid-1;tot=lmin(tot,k-zz);
        }
        else
        {
            tot=0;break;
        }
    }
    printf("%lld",tot);
    return 0;
}