0分求助

Hiraeth @ 2019-06-14 12:29:04

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,mid,R[200005],L[200005];
int sum_v[200005],sum_w[200005];
long long ans=0x3f3f3f3f3f3f3f3f,s,tmp_v,tmp_w,tmp,v[200005],w[200005];
bool check(int p){
    memset(sum_v,0,sizeof(sum_v));
    memset(sum_w,0,sizeof(sum_w));
    tmp_v=0;tmp_w=0;tmp=0;
    for (int i=1;i<=n;i++)
        if (w[i]>=p) sum_w[i]=sum_w[i-1]+w[i],sum_v[i]=sum_v[i-1]+v[i];
        else  sum_w[i]=sum_w[i-1],sum_v[i]=sum_v[i-1];
    for (int i=1;i<=m;i++){
        tmp_v=sum_v[R[i]]-sum_v[L[i-1]];
        tmp_w=sum_w[R[i]]-sum_w[L[i-1]];
        tmp+=tmp_w*tmp_v;
    }
    ans=min(ans,llabs(tmp-s));
    if (tmp>s) return false;
    return true; 
}
int main(){
    scanf("%d%d%lld",&n,&m,&s);
    for (int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]);
    for (int i=1;i<=m;i++)
        scanf("%d%d",&L[i],&R[i]);
    l=0;r=1e6;
    while (l<r){
        mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
} 

by Robert2259960864 @ 2019-06-14 12:38:53

@Hiraeth if (w[i]>=p) sum_w[i]=sum_w[i-1]+w[i]应该是＋１，因为是要求的是数量，而不是w和（再读一下题目，或者是不是手残了～）多检查两遍就好啦

by Robert2259960864 @ 2019-06-14 12:40:49

还有再％dalao，能为怒刷了100道黑题的dalao解决问题是我的荣幸ヽ(✿ﾟ▽ﾟ)ノ

by 红色OI再临 @ 2019-06-14 12:41:33

@Robert2259960864 %%%

by Robert2259960864 @ 2019-06-14 12:44:21

@红色OI再临 也％一下这位目前通过222道题的dalao (๑•̀ㅂ•́)و✧

by Hiraeth @ 2019-06-14 23:57:14

@Robert2259960864 还是错的

附新代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,R[200005],L[200005];
long long mid,sum_v[200005],sum_w[200005],l,r,ans=0x3f3f3f3f3f3f3f3f,s,tmp_v,tmp_w,tmp,v[200005],w[200005];
bool check(int p){
    memset(sum_v,0,sizeof(sum_v));
    memset(sum_w,0,sizeof(sum_w));
    tmp_v=0;tmp_w=0;tmp=0;
    for (int i=1;i<=n;i++)
        if (w[i]>=p) sum_w[i]=sum_w[i-1]+1,sum_v[i]=sum_v[i-1]+v[i];
        else  sum_w[i]=sum_w[i-1],sum_v[i]=sum_v[i-1];
    for (int i=1;i<=m;i++){
        tmp_v=sum_v[R[i]]-sum_v[L[i-1]];
        tmp_w=sum_w[R[i]]-sum_w[L[i-1]];
        tmp+=tmp_w*tmp_v;
    }
    ans=min(ans,llabs(tmp-s));
    if (tmp>s) return false;
    return true; 
}
int main(){
    scanf("%d%d%lld",&n,&m,&s);
    for (int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]);
    for (int i=1;i<=m;i++)
        scanf("%d%d",&L[i],&R[i]);
    l=0;r=0x3f3f3f3f3f3f3f3f;
    while (l<r){
        mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
} 

by Hiraeth @ 2019-06-15 00:08:32

#include<bits/stdc++.h>
using namespace std;
int n,m,R[200005],L[200005];
long long mid,sum_v[200005],sum_w[200005],l,r,ans=0x3f3f3f3f3f3f3f3f,s,tmp_v,tmp_w,tmp,v[200005],w[200005];
bool check(int p){
    memset(sum_v,0,sizeof(sum_v));
    memset(sum_w,0,sizeof(sum_w));
    tmp_v=0;tmp_w=0;tmp=0;
    for (int i=1;i<=n;i++)
        if (w[i]>=p) sum_w[i]=sum_w[i-1]+1,sum_v[i]=sum_v[i-1]+v[i];
        else  sum_w[i]=sum_w[i-1],sum_v[i]=sum_v[i-1];
    for (int i=1;i<=m;i++){
        tmp_v=sum_v[R[i]]-sum_v[L[i-1]-1];
        tmp_w=sum_w[R[i]]-sum_w[L[i-1]-1];
        tmp+=tmp_w*tmp_v;
    }
    ans=min(ans,llabs(tmp-s));
    if (tmp>s) return false;
    return true; 
}
int main(){
    scanf("%d%d%lld",&n,&m,&s);
    for (int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]);
    for (int i=1;i<=m;i++)
        scanf("%d%d",&L[i],&R[i]);
    l=0;r=0x3f3f3f3f3f3f3f3f;
    while (l<r){
        mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}