求助!!90分qwq

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

哈娜 @ 2019-08-24 15:28:55

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct ore{
    int w,v; 
}a[200001];
int n,m,r1=-1,l1=2147483647;
long long s,ans,y;
int l[200001],r[200001],pre[200001],va[200001];
int work(int mid)
{
    y=0;
    memset(pre,0,sizeof(pre));//记录前i个矿石中大于W的个数 
    memset(va,0,sizeof(va));  // 大于W的矿石总价值 
    for(int i=1;i<=n;++i)
        if(a[i].w>=mid) {pre[i]=pre[i-1]+1;va[i]=va[i-1]+a[i].v;}
        else {pre[i]=pre[i-1];va[i]=va[i-1];}  //前缀和处理数据节约空间 
    for(int i=1;i<=m;++i)
        y+=(pre[r[i]]-pre[l[i]-1])*(va[r[i]]-va[l[i]-1]);
}
int main()
{
    cin>>n>>m>>s;            //矿石个数    区间个数     比较值
    for(int i=1;i<=n;++i)
     {
        cin>>a[i].w>>a[i].v;  //重量   价值 
        if(a[i].w>r1) r1=a[i].w;
        if(a[i].w<l1) l1=a[i].w;
     }
    for(int i=1;i<=m;++i)
      cin>>l[i]>>r[i];      //区间端点 
    l1=l1-1;r1=r1+1;       //避免左右端点符合题意的情况 
    ans=0x3f3f3f3f3f3f3f3f;
    while(l1<=r1)
        {
            int mid=(r1+l1)/2;
            work(mid);
            if(y>s) l1=mid+1;
            if(y==s) {cout<<0;return 0;}
            if(y<s) r1=mid-1;
            y=llabs(y-s);   //int型用abs   long long用llabs 
            ans=min(ans,y);//寻找最小的值 
        }
     cout<<ans;
    return 0;
}

by 萧萧尹 @ 2019-10-03 13:47:03

和你错的一样 我也很迷


by hszsfzlxj @ 2019-11-05 17:32:39

前缀和数组要开long long


|