求dalao查错

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

GMSD @ 2018-12-16 20:20:44

#include<bits/stdc++.h>
using namespace std;

int number,m,Min=9999999,l=9999999,r=0,L[300002],R[300002],sum=0,pv[300002],pw[300002],bj;
struct node{
    int v,weight;
}st[300002];

int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

int check(int mid){
    memset(pv,0,sizeof(pv));
    memset(pw,0,sizeof(pw));
    sum=0;
    for(int i=1;i<=number;i++){
        if(st[i].weight>=mid)pv[i]=pv[i-1]+1,pw[i]=pw[i-1]+st[i].v;
        else pv[i]=pv[i-1],pw[i]=pw[i-1];
    }
    for(int i=1;i<=m;i++)sum+=(pv[R[i]]-pv[L[i]-1])*(pw[R[i]]-pw[L[i]-1]);
    if(sum>bj)return 1;
    else return 0;
}

int main(){
    number=read();m=read();bj=read();
    for(int i=1;i<=number;i++)st[i].weight=read(),st[i].v=read(),l=min(l,st[i].weight),r=max(r,st[i].weight);
    for(int i=1;i<=m;i++)L[i]=read(),R[i]=read();
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))l=mid+1;
        else r=mid-1;
        Min=min(abs(sum-bj),Min);
    }
    cout<<Min;
    return 0;
}

|