0分代码，能过样例，求助各位神犇（悬关）

Zhang_yuxing @ 2024-05-11 11:06:30

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long s,mid,sum,ans,W,maxw=-1,minw=100000000,minn=100000000;
long long w[200100],v[200100],l[200100],r[200100],prv[200100],prw[200100];
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        maxw=max(maxw,w[i]);
        minw=min(minw,w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
    }
    while(minw<=maxw)
    {
        mid=(minw+maxw)/2;
        ans=0;
        for(int i=1;i<=n;i++)
        {
            if(w[i]>mid)
            {
                prw[i]=prw[i-1]+1;
                prv[i]=prv[i-1]+v[i];
            }
            else
            {
                prw[i]=prw[i-1];
                prv[i]=prv[i-1];
            }
        }
        for(int i=1;i<=m;i++)
        {
            sum+=(prw[r[i]]-prw[l[i]-1])*(prv[r[i]]-prv[l[i]-1]);
        }
        ans=s-sum;
        if(ans)
        {
            maxw=mid-1;
        }
        else
        {
            minw=mid+1; 
        }
        minn=min(minn,abs(ans));
    }
    cout<<minn;
    return 0;
}

by nanfeng2233 @ 2024-05-24 21:33:42

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long s,mid,sum,ans,W,maxw,minw;
long long w[200100],v[200100],l[200100],r[200100],prv[200100],prw[200100];
int main()
{
    cin>>n>>m>>s;
    W=s;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        maxw=max(maxw,w[i]);
        //minw=min(minw,w[i]);
    }
    minw=1;
    maxw++;
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
    }
    while(minw<maxw)
    {
        memset(prw,0,sizeof(prw));
        memset(prv,0,sizeof(prv));
        mid=(minw+maxw)>>1;
        sum=0;
        for(int i=1;i<=n;i++)
        {
            if(w[i]>=mid)
            {
                prw[i]=prw[i-1]+1;
                prv[i]=prv[i-1]+v[i];
            }
            else
            {
                prw[i]=prw[i-1];
                prv[i]=prv[i-1];
            }
        }
        for(int i=1;i<=m;i++)
        {
            sum+=(long long)(prw[r[i]]-prw[l[i]-1])*(prv[r[i]]-prv[l[i]-1]);
        }
        if(sum==s)
        {
            W=0;
            break;
        }
        ans=s-sum;
        if(ans>=0)
        {
            maxw=mid;
        }
        else
        {
            minw=mid+1; 
        }
        W=min(W,abs(ans));
    }
    cout<<W;
    return 0;
}

稍微改了一点点，原代码的sum在循环的时候没有进行初始化为0，还有就是前缀和数组每次循环都需要重置。现在可以过了AC

by nanfeng2233 @ 2024-05-24 21:34:37

@Lucermaire

by Zhang_yuxing @ 2024-05-24 21:37:42

@nanfeng2233 明白啦，非常感谢ヾ(@^▽^@)ノ

by YiKangJi @ 2024-06-25 09:30:06

@lucermaire

by YiKangJi @ 2024-06-25 09:30:48

@YiKangJi 手滑了，请不要在意（删不了）