题解 P1314 【聪明的质监员】

· · 题解

既然有那么多dalao发了优质的题解，那我就来一发代码吧。

注明 本题解为纯代码，注释不多，主要是提供一段可读性强的代码，配合其他题解食用更佳。

代码1 可读性较强

#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
lld n,m,s;
lld w[200010],v[200010],l[200010],r[200010];//w,v,l,r就是原题的意思 
lld sumv[200010],sumn[200010];//vi的前缀和，个数的前缀和 
lld maxx,minn=0x7f7f7f7f7f,out=0x7f7f7f7f7f;//最大重量和最小重量 
lld Y(int W) {
    lld ans=0;
    for(lld i=1; i<=n; i++) {
        if(w[i]>=W) {
            sumv[i]=sumv[i-1]+v[i];
            sumn[i]=sumn[i-1]+1;
        }
        else {
            sumv[i]=sumv[i-1];
            sumn[i]=sumn[i-1];
        }
    }//前缀和 
    //公式求解每个区间的Y值之和 
    for(int i=1; i<=m; i++) 
        ans+=(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]); 
    return ans;
}
int main()
{
    cin>>n>>m>>s;
    for(lld i=1; i<=n; i++) {
        cin>>w[i]>>v[i];
        if(w[i]>maxx) maxx=w[i];
        if(w[i]<minn) minn=w[i];
    }
    for(lld i=1; i<=m; i++) cin>>l[i]>>r[i];
    lld left=minn-1,right=maxx+2,mid,op,low;//确定边界
    while(left<=right) {//二分 
        mid=(left+right)/2,op=Y(mid),low=fabs(s-op);
        if(op>s) left=mid+1;
        else right=mid-1;
        if(low<out) out=low;
    }
    cout<<out;
    return 0;
}

代码2 较为精简（无注释）其实就是压行了一下

#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
lld n,m,s;
lld w[200010],v[200010],l[200010],r[200010],sumv[200010],sumn[200010],maxx,minn=0x7f7f7f7f7f,out=0x7f7f7f7f7f;
lld Y(int W) {
    lld ans=0;
    for(lld i=1; i<=n; i++) {
        if(w[i]>=W) {sumv[i]=sumv[i-1]+v[i],sumn[i]=sumn[i-1]+1;}
        else {sumv[i]=sumv[i-1],sumn[i]=sumn[i-1];}
    }  
    for(int i=1; i<=m; i++) ans+=(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]); 
    return ans;
}
int main()
{
    cin>>n>>m>>s;
    for(lld i=1; i<=n; i++) {cin>>w[i]>>v[i];if(w[i]>maxx) maxx=w[i];if(w[i]<minn) minn=w[i];}
    for(lld i=1; i<=m; i++) cin>>l[i]>>r[i];
    lld left=minn-1,right=maxx+2,mid,op,low;
    while(left<=right) {
        mid=(left+right)/2,op=Y(mid),low=fabs(s-op);
        if(op>s) left=mid+1;else right=mid-1;
        if(low<out) out=low;
    }
    cout<<out;
    return 0;
}

A了这道题，祝你们成功（手动滑稽）（玩梗）