求助！！！

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

rome_empire @ 2023-01-06 00:37:22

#include<bits/stdc++.h>
using namespace std;
long long n,m,s;
long long l[200005],r[200005];
long long w[200005],v[200005];
long long ans=0x3f3f3f3f3f3f3f3f;//终究是不够大 
long long bks,rxy,sumn;
long long maxn=-1,minn=2147483647;
long long q_st[200005],q_ed[200005]; 
int check(int base)
{
    int c1=0,c2=0;
    rxy=0,sumn=0;
    memset(q_st,0,sizeof(q_st));
    memset(q_ed,0,sizeof(q_ed));
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=base)
        {
            q_st[i]=q_st[i-1]+1;
            q_ed[i]=q_ed[i-1]+v[i];
        }
        else
        {
            q_st[i]=q_st[i-1];
            q_ed[i]=q_ed[i-1];
        }
    } 

    for(int i=1;i<=m;i++)
    {
        c1=q_st[r[i]]-q_st[l[i]-1];
        c2=q_ed[r[i]]-q_ed[l[i]-1];
        sumn+=c1*c2;
    }

    rxy=llabs(sumn-s);//long long の abs 
    if(sumn>s)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]);
        scanf("%lld",&v[i]);
        minn=min(minn,w[i]);
        maxn=max(maxn,w[i]);
    }

    minn=minn-1;
    maxn=maxn+1;//保个险...

    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&l[i]);
        scanf("%lld",&r[i]);
    }

    int zuo=minn,you=maxn;
    int mid;
    while(zuo<=you)
    {
        mid=(zuo+you)/2;
        if(check(mid))
        {
            //ans=rxy;
            zuo=mid+1;          
        }
        else
        {
            you=mid-1;
        }
        if(rxy<ans)
        {
            ans=rxy; //择最优 
        }
    }
    cout<<ans;
    return 0;
} 

为啥错了第6个点和第20个点QAQ

by 崔泽禹 @ 2023-01-06 07:36:09

AC代码可以参考一下

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int M = 2e5 + 5;
int n, m, x, y, mid;
int w[N], v[N];
int l[M], r[M];
long long s;
long long ans;
long long sum;
long long pw[N], pv[N];
int main() {
    cin >> n >> m >> s;
    ans = s;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
        y = max(y, w[i]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i];
    }
    x = 0;
    y++;
    while (x < y) {
        memset(pw, 0, sizeof(pw));
        memset(pv, 0, sizeof(pv));
        mid = (x + y) >> 1;
        sum = 0;
        for (int i = 1; i <= n; i++) {
            if (w[i] > mid) {
                pw[i] = pw[i - 1] + 1;
                pv[i] = pv[i - 1] + v[i]; 
            } else {
                pw[i] = pw[i - 1];
                pv[i] = pv[i - 1]; 
            }
        }
        for (int i = 1; i <= m; i++) {
            sum += (long long)(pw[r[i]] - pw[l[i] - 1]) * (pv[r[i]] - pv[l[i] - 1]);
        }
        if (sum == s) {
            ans = 0;
            break;
        } else {
            ans = min(ans, abs(sum - s));
            if (sum <= s) {
                y = mid;
            } else {
                x = mid + 1;
            }
        }
    }
    cout << ans;
    return 0;
}