死循环qwq(无从下手.jpg)

赵灵儿 @ 2018-04-19 11:22:38

#include<bits/stdc++.h>
#define N 200010
using namespace std;
namespace program{
    int ans=20021109,w[N],Val[N],fw[N],l[N],r[N],n,m,S;
    inline int check(int x){
        int res=0;
        for(int i=1;i<=m;i++){
            if(r[i]<x)
                continue;
            else if(r[i]>=x)
                res+=(fw[r[i]]-fw[x-1])*(r[i]-x+1);
        }
        return res;
    }
    inline void work(){
        scanf("%d%d%d",&n,&m,&S);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&w[i],&Val[i]);
        for(int i=1;i<=m;i++)
            scanf("%d%d",&l[i],&r[i]);
        fw[0]=0;
        for(int i=1;i<=n;i++)
            fw[i]=fw[i-1]+Val[i];
        int L=1,R=n;
        while(L<R){
            int mid=(L+R)>>1;
            int sum=check(mid);
            if(sum>S)
                L=mid;
            else
                R=mid+1;
            ans=min(ans,abs(sum-S));
//          printf("%d\n",ans);
        }
        printf("%d\n",ans);
    }
}
int main(){
    program::work();
    return 0;
}

by 赵灵儿 @ 2018-04-19 11:24:39

是二分炸了，然而怎么改啊qwq

by 赵灵儿 @ 2018-04-19 11:41:53

不是死循环了然而0分qwq

#include<bits/stdc++.h>
#define N 200010
using namespace std;
namespace program{
    int ans=20021109,w[N],Val[N],fw[N],l[N],r[N],n,m,S;
    inline int check(int x){
        int res=0;
        for(int i=1;i<=m;i++){
            if(r[i]<x)
                continue;
            else if(r[i]>=x)
                res+=(fw[r[i]]-fw[x-1])*(r[i]-x+1);
        }
        return res;
    }
    inline void work(){
        scanf("%d%d%d",&n,&m,&S);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&w[i],&Val[i]);
        for(int i=1;i<=m;i++)
            scanf("%d%d",&l[i],&r[i]);
        fw[0]=0;
        for(int i=1;i<=n;i++)
            fw[i]=fw[i-1]+Val[i];
        int L=1,R=n;
        while(L<R){
            int mid=(L+R)>>1;
            int sum=check(mid);
            if(sum>S)
                L=mid+1;
            else
                R=mid;
            ans=min(ans,abs(sum-S));
//          printf("%d\n",ans);
        }
        printf("%d\n",ans);
    }
}
int main(){
    program::work();
    return 0;
}
/*
10 10 1475400
23954 25180
18805 2701
17195 5663
7044 13659
8139 30927
19774 25516
7472 4572
5999 6166
1185 13621
10414 26521
2 10
4 7
5 8
1 6
2 7
1 3
2 7
3 4
1 6
1 10
*/

by 赵灵儿 @ 2018-04-19 12:11:32

哦不好意思我似乎看错题目了，竟然把w看成了矿石编号qwq

by 赵灵儿 @ 2018-04-19 13:20:05

25分qwq

#include<bits/stdc++.h>
#define int long long
#define N 200010
using namespace std;
namespace program{
    int ll,rr,w[N],val[N],l[N],r[N];
    int fnum[N],fval[N],ans=20021109;
    int n,m,s;
    inline int check(int x){
        memset(fnum,0,sizeof fnum);
        memset(fval,0,sizeof fval);
        for(int i=1;i<=n;i++){
            if(w[i]>=x)
                fnum[i]=fnum[i-1]+1,fval[i]=fval[i-1]+val[i];
            else
                fnum[i]=fnum[i-1],fval[i]=fval[i-1];
        }
        int oo=0;
        for(int i=1;i<=m;i++)
            oo+=(fnum[r[i]]-fnum[l[i]-1])*(fval[r[i]]-fval[l[i]-1]);
        return oo;  
    }
    inline void work(){
        scanf("%lld%lld%lld",&n,&m,&s);
        for(int i=1;i<=n;i++)   
            scanf("%lld%lld",&w[i],&val[i]),ll=min(w[i],ll),rr=max(rr,w[i]);
        for(int i=1;i<=m;i++)
            scanf("%lld%lld",&l[i],&r[i]);
        ll-=2,rr+=2;
        while(ll<rr){
            int mid=(ll+rr)>>1;
            int sum=check(mid);
            if(sum>s)
                ll=mid+1;
            else
                rr=mid-1;
            ans=min(ans,abs(s-sum));
        }printf("%lld\n",ans);
    }
}
signed main(){
    program::work();
    return 0;
}

by 友利奈绪 @ 2018-08-18 15:32:29

ans值开大点