65分求佬助:每次写完代码,只要是不能拿全对的情况我都难以找出错误

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

32aaaaa @ 2024-12-07 15:07:59

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,MAX=INT_MIN,MIN=INT_MAX;
typedef struct 
{
    long long w;
    long long v;
}Point;
typedef struct
{
    long long l,r;
}Side;
Point point[200010];
Side side[200010];
typedef struct
{
    long long n,v;
}Sum;
Sum sum[200010];
long long result;
int m1(int w)
{
    for(int i=1;i<=n;i++) sum[i].v=sum[i].n=0;
    for(int i=1;i<=n;i++)
    {
        if(point[i].w>=w)
        {
            sum[i].v=sum[i-1].v+point[i].v;
            sum[i].n=sum[i-1].n+1;
        }
        else
        {
            sum[i].v=sum[i-1].v;
            sum[i].n=sum[i-1].n;
        }
    }
    long long y=0;
    for(int i=1;i<=m;i++)
    {
        y+=(sum[side[i].r].n-sum[side[i].l-1].n)*(sum[side[i].r].v-sum[side[i].l-1].v);
    }
    result=abs(y-s);
    if(y>s)return 1;
    return 0;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        long long w,v;cin>>w>>v;
        point[i].w=w;
        point[i].v=v;
        MAX=max(MAX,w);
        MIN=min(MIN,w);
    }
    for(int i=1;i<=m;i++) cin>>side[i].l>>side[i].r;
    long long left=MIN,right=MAX,mid;
    long long ans=INT_MAX;
    while(left<=right)
    {
        mid=(left+right)/2;
        int judge=m1(mid);
        if(judge)//y>s
        {
            left=mid+1;
        }
        else//y<=s
        {
            right=mid-1;
        }
        if(result<ans) ans=result;
    }
    cout<<ans<<endl;
    return 0;
}

|