求大佬帮忙 WA了5个点 我也是醉啦

Ning_Mew @ 2017-09-28 17:03:31

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
LL read()
{
    LL x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
LL n,m,S,w[200000+10],v[200000+10];
LL qu[200000+10][3];
LL start=0,tail=0,mid;
LL ans=999999999999999;
///////////max
LL max(LL a,LL b)
    {return a>b?a:b;}
///////////min
LL min(LL a,LL b)
    {return a<b?a:b;}
///////////abs
LL abss(LL k)
{
    if(k<0)return -k;
    return k;
}
///////////check
LL check(LL W)
{
    LL re=0,numb[200000+10],vel[200000+10];
    memset(numb,0,sizeof(numb));
    memset(vel,0,sizeof(vel));
    for(int i=1;i<=n;i++)
    {
        numb[i]=numb[i-1];vel[i]=vel[i-1];
        if(w[i]>=W){numb[i]+=1;vel[i]+=v[i];}
    }
    for(int i=1;i<=m;i++)
    {
        LL V=0,num=0;
        V =  vel[qu[i][2]] - vel[qu[i][1]-1];
        num= numb[qu[i][2]]- numb[qu[i][1]-1];
        re+=V*num;
    }
    return re;
}
int main()
{
    freopen("qc.in","r",stdin);
    n=read();m=read();S=read();
    for(int i=1;i<=n;i++)
    {
        w[i]=read();v[i]=read();
        tail=max(tail,w[i]);
    }
    cout<<tail<<endl;
    for(int i=1;i<=m;i++)
        {qu[i][1]=read();qu[i][2]=read();}
    int Time=0;
    do
    {
        mid=(start+tail)/2;
        LL box=check(mid);
        //cout<<mid<<' '<<box<<endl;
        if(box>S){start=mid+1;}
        if(box<S){tail=mid-1;}
        if(box==S){ans=0;break;}
        ans=min(ans,abss(box-S));
    }while(start<tail);
    cout<<ans;
    return 0;
}

by Ning_Mew @ 2017-09-28 17:04:05

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
LL read()
{
    LL x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
LL n,m,S,w[200000+10],v[200000+10];
LL qu[200000+10][3];
LL start=0,tail=0,mid;
LL ans=999999999999999;
///////////max
LL max(LL a,LL b)
    {return a>b?a:b;}
///////////min
LL min(LL a,LL b)
    {return a<b?a:b;}
///////////abs
LL abss(LL k)
{
    if(k<0)return -k;
    return k;
}
///////////check
LL check(LL W)
{
    LL re=0,numb[200000+10],vel[200000+10];
    memset(numb,0,sizeof(numb));
    memset(vel,0,sizeof(vel));
    for(int i=1;i<=n;i++)
    {
        numb[i]=numb[i-1];vel[i]=vel[i-1];
        if(w[i]>=W){numb[i]+=1;vel[i]+=v[i];}
    }
    for(int i=1;i<=m;i++)
    {
        LL V=0,num=0;
        V =  vel[qu[i][2]] - vel[qu[i][1]-1];
        num= numb[qu[i][2]]- numb[qu[i][1]-1];
        re+=V*num;
    }
    return re;
}
int main()
{
    freopen("qc.in","r",stdin);
    n=read();m=read();S=read();
    for(int i=1;i<=n;i++)
    {
        w[i]=read();v[i]=read();
        tail=max(tail,w[i]);
    }
    //cout<<tail<<endl;
    for(int i=1;i<=m;i++)
        {qu[i][1]=read();qu[i][2]=read();}
    int Time=0;
    do
    {
        mid=(start+tail)/2;
        LL box=check(mid);
        //cout<<mid<<' '<<box<<endl;
        if(box>S){start=mid+1;}
        if(box<S){tail=mid-1;}
        if(box==S){ans=0;break;}
        ans=min(ans,abss(box-S));
    }while(start<tail);
    cout<<ans;
    return 0;
}

by Ning_Mew @ 2017-09-28 17:04:21

看第二份代码

by moye到碗里来 @ 2017-09-28 17:12:55

你的S是啥啊

by moye到碗里来 @ 2017-09-28 17:13:46

我给你看看我的吧

by moye到碗里来 @ 2017-09-28 17:15:17

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=200100;
LL ans=0x3f3f3f3f3f3f3f3f;
LL sw[N],sv[N],w[N],v[N];
int l[N],r[N];
int n,m;
LL S;
LL f(LL a,LL b){
    return a>b?a-b:b-a;
}
bool check(LL mid){
    for (int i=1;i<=n;i++){
        sw[i]=sw[i-1]+(w[i]>=mid);
        sv[i]=sv[i-1]+(w[i]>=mid)*v[i];
    }
    LL W=0;
    for (int i=1;i<=m;i++){
        W+=(sw[r[i]]-sw[l[i]-1])*(sv[r[i]]-sv[l[i]-1]);
    }
    ans=min(ans,f(W,S));
    return W<=S;
}
int main(){
    scanf("%d%d%lld",&n,&m,&S);
    LL Left=0,Right=0;
    for (int i=1;i<=n;i++){
        scanf("%lld%lld",&w[i],&v[i]);
        Right=max(Right,w[i]);
    }
    Right++;
    for (int i=1;i<=m;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    while (Left+1<Right){
        int mid=(Left+Right)>>1;
        if (check(mid))Right=mid;
            else Left=mid;
    }
    check(Left);check(Right);
    printf("%lld",ans);
    return 0;
}

by moye到碗里来 @ 2017-09-28 17:21:23

话说我这个还是照着题解敲得。。我自己在敲一遍吧。。

by Ning_Mew @ 2017-09-29 19:51:05

@ moye到碗里来 我改完了，还是谢谢了

by wangzhifang @ 2019-03-16 21:17:05

@Ning_Mew +1 我的评测记录

by wangzhifang @ 2019-03-16 21:17:20

#include <cstdio>
#include <cmath>
#include <algorithm>
#define max_n 200000
#define max_m 200000
#define max_w 1000000
using namespace std;
int w[max_n+1],v[max_n+1],l[max_m+1],r[max_m+1];
long long prev[max_n+1],pren[max_n+1];
bool check(int x,int n,int m,long long s,long long&ans){
    int i;
    long long y;
    prev[0]=pren[0]=0;
    for(i = 1; i <= n; i ++){
        if(w[i]>=x)
            prev[i]=prev[i-1]+v[i],pren[i]=pren[i-1]+1;
        else
            prev[i]=prev[i-1],pren[i]=pren[i-1];
    }
    y=0;
    for(i = 1; i <= m; i ++){
        y+=(prev[r[i]]-prev[l[i]-1])*(pren[r[i]]-pren[l[i]-1]);
        if(y>=s*2)
            return 1;
    }
    ans=min(ans,llabs(y-s));
    return y>s;
}
int main(){
    int n,m,i,_l,_r,mid,minw,maxw;
    long long s,ans;
    scanf("%d%d%lld",& n,& m,& s);
    maxw=0,minw=max_w;
    for(i = 1; i <= n; i ++){
        scanf("%d%d",w+i,v+i);
        minw=min(minw,w[i]);
        maxw=max(maxw,w[i]);
    }
    for(i = 1; i <= m; i ++)
        scanf("%d%d",l+i,r+i);
    ans=s;
    _l=minw-2,_r=maxw+1;
    while(_l+1<_r-1){
        mid=(_l+_r)>>1;
        if(check(mid,n,m,s,ans))
            _l=mid;
        else
            _r=mid;
    }
    printf("%lld\n",ans);
    return 0;
}