50分求助

P1314 [NOIP2011 提高组] 聪明的质监员

狂丿Kurumi @ 2019-04-15 21:08:13

50分,求大佬帮忙查错

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int w[N],v[N],l[N],r[N];
long long pren[N],prev[N];
long long Y,s,sum;
int n,m,mx=-1,mn=0x3f3f3f3f;
bool check(int W)
{
    Y=0,sum=0;
    memset(pren,0,sizeof(pren));
    memset(prev,0,sizeof(prev));
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=W)pren[i]=pren[i-1]+1,prev[i]=prev[i-1]+v[i];
        else pren[i]=pren[i-1],prev[i]=prev[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        Y+=(pren[r[i]]-pren[l[i]-1])*(prev[r[i]]-prev[l[i]-1]);
    }
    sum=llabs(Y-s);
    if(Y>s)return 1;
    else return 0;;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        mx=max(mx,w[i]);
        mn=min(mn,w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
    }
    int left=mn-1,rigth=mx+2,mid;
    long long ans=0x3f3f3f3f;
    while(left<rigth)
    {
        mid=(left+rigth)>>1;
        if(check(mid))left=mid+1;
        else rigth=mid-1;
        if(sum<ans) ans=sum;
    }
    cout<<ans;
    return 0;
 } 

by nofind @ 2019-04-19 21:40:00

@狂丿Kurumi ans开太小了,你看S的范围


|