23 条题解

  • 2
    @ 2017-10-19 22:18:00

    用两个前缀和优化

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <cmath>
    #define LL long long
    using namespace std;
    template <class _T> inline void read(_T &_x) {
        int _t; bool _flag=false;
        while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
        if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
        while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
        if(_flag) _x=-_x;
    }
    const int maxn=200005;
    LL le,ri,mid,s,sumn[maxn],sumv[maxn],ans=0x3f3f3f3f3f3f;
    int n,m,w[maxn],v[maxn],l[maxn],r[maxn];
    bool check(LL x){
        LL tmp=0;
        for(int i=1;i<=n;i++){
            sumn[i]=sumn[i-1]+(x<=w[i]? 1:0);
            sumv[i]=sumv[i-1]+(x<=w[i]? v[i]:0);
        }
        for(int i=1;i<=m;i++){
            tmp+=(sumv[r[i]]-sumv[l[i]-1])*(sumn[r[i]]-sumn[l[i]-1]);
        }
        if(ans>abs(s-tmp))ans=abs(s-tmp);
        if(s>tmp)return true;
        return false;
    }
    int main(){
        read(n),read(m),read(s);
        for(int i=1;i<=n;i++){
            read(w[i]),read(v[i]);
            if(w[i]>ri)ri=w[i];
        } 
        ri++;
        for(int i=1;i<=m;i++){
            read(l[i]),read(r[i]);
        }
        le=0;
        while(le<ri){
            mid=le+ri>>1;
            if(!check(mid))le=mid+1;
            else ri=mid;
        }
        printf("%lld",ans);
        
        return 0;
    }
    
  • 2
    @ 2012-10-09 10:52:15

    二分+一点点的优化

    注意数据是比较大的,最大的检测值之和为2*10^6*10^6*2*10^6...

    最好将不是循环变量的类型都弄成int64;

    还有当算检测值之和时当>=s*3,就直接退出,因为这足以说明不可能为更优

  • 1
    @ 2017-10-27 16:56:31

    二分+前缀和模拟

    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <cctype>
    #include <vector>
    #include <queue>
    using namespace std;
    long long n,m,s,l,r,mid,t,ans=1e13,y=0;
    long long w[200001],v[200001],ll[200001];
    long longrr[200001],x[200001],vv[200001];
    bool check(int mid)
    {
        for(int i=1;i<=n;i++)
        {
            if(w[i]>=mid)
            {
                x[i]=x[i-1]+1;
                v[i]=v[i-1]+vv[i];
            }
            else
            {
                x[i]=x[i-1];
                v[i]=v[i-1];
            }
        }
        for(int i=1;i<=m;i++)
        {
            y+=(x[rr[i]]-x[ll[i]-1])*(v[rr[i]]-v[ll[i]-1]);
        }
        t=s-y;
        y=0;
        if(t>0)
        {
            return true;
        }
        else if(t<0)
        {
            return false;
        }
        else
        {
            printf("0");
            exit(0);
        }
    }
    int main()
    {
        scanf("%I64d%I64d%I64d",&n,&m,&s);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&w[i],&vv[i]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%lld%lld",&ll[i],&rr[i]);
        }
        l=0;
        r=1e6+1;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(check(mid)==true)
            {
                if(labs(t)<ans)
                {
                    ans=labs(t);
                }
                r=mid-1;
            }
            else
            {
                if(labs(t)<ans)
                {
                    ans=labs(t);
                }
                l=mid+1;
            }
        }
        printf("%lld",ans);
        return 0;
    }
    
  • 1
    @ 2017-08-22 14:09:25
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,m;
    int w[200000+1];
    int v[200000+1];
    int le[200000+1];
    int ri[200000+1];
    double s;
    double s_w[200000+1];
    double s_v[200000+1];
    
    double calc_1(int x)
    {
        memset(s_w,0,sizeof(s_w));
        memset(s_v,0,sizeof(s_v));
        for (int i=1;i<=n;i++)
        {
            s_w[i]=s_w[i-1]+((w[i]>=x)?1:0);
            s_v[i]=s_v[i-1]+((w[i]>=x)?v[i]:0);
        }
        double ans=0;
        for (int i=1;i<=m;i++)
            ans+=((s_w[ri[i]]-s_w[le[i]-1])*(s_v[ri[i]]-s_v[le[i]-1]));
        return ans;
    }
    
    int main()
    {
        while (~scanf("%d%d%lf",&n,&m,&s))
        {
            int l=oo_max,r=oo_min;
            memset(w,0,sizeof(w));
            memset(v,0,sizeof(v));
            for (int i=1;i<=n;i++)
            {
                scanf("%d%d",&w[i],&v[i]);
                l=min(l,w[i]),r=max(r,w[i]);
            }
            memset(le,0,sizeof(le));
            memset(ri,0,sizeof(ri));
            for (int i=1;i<=m;i++)
                scanf("%d%d",&le[i],&ri[i]);
            while (r-l>1)
            {
                int mid=(l+r)/2;
                double sum=calc_1(mid);
                if (s<sum)
                    l=mid;
                else
                    r=mid;
            }
            double ans_l=fabs(s-calc_1(l)),ans_r=fabs(s-calc_1(r));
            double ans=min(ans_l,ans_r);
            printf("%.0lf\n",ans);
        }
    }
    
  • 0
    @ 2017-11-04 08:30:48

    树状数组计算检验二分结果
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    #define ll long long
    using namespace std;

    const int N=2e5+5;
    ll n,m,s;
    ll sz[N][2];
    ll L[N],R[N];
    ll w[N],v[N];

    void add(int x,ll a,int kind){
    for(int i=x;i<=n;i+=i&-i){
    sz[i][kind]+=a;
    }
    }

    ll qiu(ll x,int kind){
    ll cnt=0;
    for(int i=x;i;i-=i&-i){
    cnt+=sz[i][kind];
    }
    return cnt;
    }

    ll check(ll x){
    memset(sz,0,sizeof(sz));
    for(int i=1;i<=n;i++){
    if(w[i]>=x) add(i,(ll)v[i],1),add(i,(ll)1,0);
    }
    ll ans=0;
    for(int i=1;i<=m;i++){
    int l=L[i],r=R[i];
    ans+=(qiu(r,0)-qiu(l-1,0))*(qiu(r,1)-qiu(l-1,1));
    }
    return ans;
    }

    int main()
    {
    // freopen("test.in","r",stdin);
    ll maxn=-1;
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&w[i],&v[i]),maxn=max(maxn,w[i]);
    for(int i=1;i<=m;i++){
    scanf("%lld%lld",&L[i],&R[i]);
    }
    // for(int i=0;i<=maxn;i++) printf("%lld\n",check(i));
    ll l=-1,r=maxn;
    ll last=0x3f3f3f3f3f3f3f3f;
    while(l<r){
    ll mid=l+r>>1;
    ll tt=check(mid),kk=fabs(tt-s);
    last=min(last,kk);
    if(tt<=s) r=mid;
    else l=mid+1;
    }
    printf("%lld",last);
    return 0;
    }

  • 0
    @ 2016-10-12 20:42:34

    二分,在求每次的W时先把整体算出来

    #include<cstdio>
    #include<iostream>
    using namespace std;
    long long n,m,w[200005],v[200005],L[200005],R[200005],sum[200005]={0},sumv[200005]={0};
    long long s,Y,minin=0x3f3f3f3f;
    long long lef=0x3f3f3f3f,righ=-1;
    long long asb(long long a){
    if(a>=0) return a;
    return -a;
    }
    long long check(long long W){
    long long temp=0,i;
    for(i=1;i<=n;i++){
    if(w[i]>=W) {
    sum[i]=sum[i-1]+1;
    sumv[i]=sumv[i-1]+v[i];
    }
    else{
    sum[i]=sum[i-1];
    sumv[i]=sumv[i-1];
    }
    }
    for(i=1;i<=m;i++){
    temp+=(sum[R[i]]-sum[L[i]-1])*(sumv[R[i]]-sumv[L[i]-1]);
    }
    return temp;
    }
    int main(){
    //freopen("qc20.in","r",stdin);
    long long i,j;
    scanf("%lld %lld %lld",&n,&m,&s);
    for(i=1;i<=n;i++){
    scanf("%lld %lld",&w[i],&v[i]);
    if(lef>w[i]) lef=w[i];
    if(righ<w[i]) righ=w[i];
    }
    for(i=1;i<=m;i++){
    scanf("%lld %lld",&L[i],&R[i]);
    }
    minin=asb(check(righ)-s);
    while(1){
    if(righ-lef==1){
    long long t1=check(lef);
    long long t2=check(righ);
    t1=asb(t1-s);t2=asb(t2-s);
    if(t1>t2) minin=t2;
    else{
    minin=t1;
    }
    break;
    }
    else{
    long long mid=(lef+righ)>>1;
    long long W=mid;
    Y=0;
    Y=check(W);
    if(minin>asb(s-Y)) minin=asb(s-Y);
    if(Y==s){
    printf("0\n");
    }
    if(Y>s) lef=mid;
    if(Y<s) righ=mid;
    }
    }
    printf("%lld\n",minin);
    return 0;
    }

  • 0
    @ 2016-09-14 19:50:30

    一眼二分题
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;

    const int maxn = 200000 + 10;
    const int maxw = 1000000 + 10;
    typedef long long LL;

    int n, m;
    LL S;
    int l[maxn], r[maxn];
    int v[maxn], w[maxn];
    LL pre_cnt[maxn], pre_sum[maxn];

    LL clt (int W) {
    LL ret = 0;

    pre_cnt[0] = pre_sum[0] = 0;
    for (int i = 1; i <= n; i++) {
    pre_cnt[i] = pre_cnt[i-1];
    pre_sum[i] = pre_sum[i-1];
    if (w[i] >= W) {
    pre_cnt[i]++;
    pre_sum[i] += v[i];
    }
    }

    for (int i = 0; i < m; i++)
    ret += (pre_cnt[r[i]]-pre_cnt[l[i]-1]) * (pre_sum[r[i]]-pre_sum[l[i]-1]);

    return ret;
    }

    int main ()
    {
    // freopen("in.txt", "r", stdin);
    cin >> n >> m >> S;
    for (int i = 1; i <= n; i++)
    scanf("%d%d", &w[i], &v[i]);
    for (int i = 0; i < m; i++)
    scanf("%d%d", &l[i], &r[i]);

    int L = *min_element(w+1, w+n+1);
    int R = *max_element(w+1, w+n+1);
    while (R - L > 1) {
    int M = L + (R-L)/2;
    if (clt(M) > S) L = M; else R = M;
    }
    LL ans = min(abs(clt(L)-S), abs(clt(R)-S));
    cout << ans;
    return 0;
    }
    ```

  • 0
    @ 2016-08-04 22:32:26

    超时了一次,竟然是因为c++的流太慢了(逃,也算是大意了吧最后一个点慢了三十多毫秒。一关闭同步就瞬间提到600ms;
    这道题是经典的二分+前缀和啦~
    二分思路应该是容易想到的,寻找w值
    不断二分更新
    关键就是怎样判断二分后继续二分范围
    即二分依据
    附上代码

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <iomanip>
    #include <cstdlib>
    using namespace std;

    long long s[200004],sv[200004];
    struct node
    {
    long long w,v;
    }a[200004];
    struct tion
    {
    long long x,y;
    }b[200004];
    long long n,m,S;

    void work(long long r)
    {
    s[0]=sv[0]=0ll;
    for(long long i=1;i<=n;i++)
    if(a[i].w>=r)
    s[i]=s[i-1]+1,sv[i]=sv[i-1]+a[i].v;
    else
    s[i]=s[i-1],sv[i]=sv[i-1];
    }

    long long cal(long long r)
    {
    long long ans=0ll;
    for(long long i=1;i<=m;i++)
    ans+=(s[b[i].y]-s[b[i].x-1])*(sv[b[i].y]-sv[b[i].x-1]);
    return ans;
    }

    int main()
    {
    ios::sync_with_stdio(false);
    long long start=0ll,end=0ll;
    cin>>n>>m>>S;
    for(int i=1;i<=n;i++)
    {cin>>a[i].w>>a[i].v;
    end=max(end,a[i].w);}
    for(int i=1;i<=m;i++)
    cin>>b[i].x>>b[i].y;
    long long ans=9223372036854775807ll;
    while(start<=end)
    {
    long long mid=(start+end)>>1;
    work(mid);

    long long t=cal(mid);
    if(abs(t-S)<ans)
    ans=abs(t-S);
    if(ans==0)
    break;
    if(S<t)
    start=mid+1;
    else
    end=mid-1;
    }
    cout<<ans<<endl;
    return 0;
    }

    Powder原著

  • 0
    @ 2016-07-23 12:03:11

    语文数学不好是硬伤。。。。
    \(\sum_{j} 1\)不是区间大小,而是区间中满足条件的数的个数。。
    我还是太渣QwQ。。

  • 0
    @ 2016-07-12 16:29:08

    其实每个区间的检验值Yi就是区间内质量大于W的个数×它们的价值之和。
    所以W和s有着单调的关系,预处理+二分,代码写的有点难看。。(数据有点大)
    ~~~
    #include <cstdio>
    const int INF=0x3f3f3f3f;
    long long n,m,s,w[200005],v[200005],l[200005],r[200005],sum[200005],sumv[200005];
    long long w_max=-1,w_min=INF;
    long long best_w,dis=INF;
    long long int test(long long W){
    long long int Y=0;
    for(int i=1;i<=n;i++)
    if(w[i]>=W){
    sum[i]=sum[i-1]+1;
    sumv[i]=sumv[i-1]+v[i];
    }
    else{
    sum[i]=sum[i-1];
    sumv[i]=sumv[i-1];
    }
    for(int j=1;j<=m;j++)
    Y+=(sum[r[j]]-sum[l[j]-1])*(sumv[r[j]]-sumv[l[j]-1]);
    return Y;
    }
    int main(){
    //freopen("input.txt","r",stdin);
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i=1;i<=n;i++){
    scanf("%lld%lld",w+i,v+i);
    if(w[i]>w_max)w_max=w[i];
    if(w[i]<w_min)w_min=w[i];
    }
    w_min--;w_max++;
    for(int i=1;i<=m;i++){
    scanf("%lld%lld",l+i,r+i);
    }
    bool flag=true;
    long long int s_max=test(w_min);
    long long int s_min=test(w_max);
    if(s_min>s){
    flag=false;
    dis=s_min-s;
    }
    if(s_max<s){
    flag=false;
    dis=s-s_max;
    }
    while(flag){
    if(w_max-w_min<=1){
    long long int t1=s-test(w_max);
    long long int t2=s-test(w_min);
    if(t1<0)t1=-t1;
    if(t2<0)t2=-t2;
    if(t1<t2) dis=t1;
    else dis=t2;
    break;
    }
    long long int W=(w_min+w_max)>>1;
    long long int Y=test(W);
    if(Y>s)w_min=W;
    else w_max=W;
    }
    printf("%lld\n",dis);
    return 0;
    }

    
    附:最后一个测试数据n=m=200000 s=9580200000
    
  • 0
    @ 2015-10-26 17:00:27

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cstdlib>
    #include<cmath>
    using namespace std;
    int n,m;
    long long S;
    long long sum[200010];
    int w[200010],v[200010];
    int suma[200010];
    int ma=0;
    long long ans=0;
    int li[200010],ri[200010];
    long long ok1=4611686018427387904;
    long long ok2=4611686018427387904;

    bool judge(int W)
    {
    ans=0;
    memset(suma,0,sizeof(suma));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
    {
    suma[i]=suma[i-1];
    sum[i]=sum[i-1];
    if(w[i]>=W){
    suma[i]++;
    sum[i]+=v[i];
    }
    }
    for(int i=1;i<=m;i++){
    ans+=(long long)(sum[ri[i]]-sum[li[i]-1])*(suma[ri[i]]-suma[li[i]-1]);
    }
    if(ans-S>0){
    if(ans-S<ok1) ok1=ans-S;
    return 0;
    }
    if(S-ans<ok2) ok2=S-ans;
    return 1;
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    scanf("%lld",&S);
    for(int i=1;i<=n;i++)
    {
    scanf("%d%d",&w[i],&v[i]);
    ma=max(ma,v[i]);
    }
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d",&li[i],&ri[i]);
    }
    int l=1,r=ma+1;
    while(l<r){
    int mid=(l+r)>>1;
    if(!judge(mid)){
    l=mid+1;
    }
    else {
    r=mid;
    }
    }
    if(ok1>ok2) cout<<ok2<<endl;
    else cout<<ok1<<endl;
    return 0;
    }

  • 0
    @ 2015-08-23 13:24:57

    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    const int MAXN = 200000 + 10;

    long long n, m, s, w[MAXN], v[MAXN], l[MAXN], r[MAXN], bri[MAXN], num[MAXN], f[MAXN];

    long long check(int x){
    long long ans = 0;
    for(int i=1; i<=n; i++){
    if(w[i] >= x){
    f[i] = f[i-1] + v[i];
    num[i] = num[i-1] + 1;
    }
    else{
    f[i] = f[i-1];
    num[i] = num[i-1];
    }
    }
    for(int i=1; i<=m; i++)
    ans += (f[r[i]] - f[l[i] - 1]) * (num[r[i]] - num[l[i] - 1]);
    return s - ans;
    }

    long long find(int s, int t){
    if(s == t)
    return abs(check(s));
    long long mid = (s + t) / 2;
    long long qiao = check(bri[mid]);
    long long ans = abs(qiao);
    if(qiao > 0)
    ans = min(find(s, mid), ans);
    else if(qiao < 0)
    ans = min(find(mid+1, t), ans);
    return ans;
    }

    int main()
    {
    scanf("%I64d%I64d%I64d", &n, &m, &s);
    for(int i=1; i<=n; i++){
    scanf("%I64d%I64d", &w[i], &v[i]);
    bri[i] = w[i];
    }
    sort(&bri[1], &bri[1]+n);
    for(int i=1; i<=m; i++)
    scanf("%I64d%I64d", &l[i], &r[i]);

    long long ans = find(1, n);
    printf("%I64d", ans);
    return 0;
    }
    二分答案 + long long

  • 0
    @ 2015-07-18 21:45:10

    program p1740;
    var
    ans,s,tot1,tot2:int64;
    i,j,l,r,mid,k,n,m,t,max:longint;
    a,b,w,v,d:array[1..300000]of longint;
    e:array[1..300000]of int64;
    c:array[1..300000]of boolean;
    begin
    ans:=1000000000000000;
    readln(n,m,s);
    for i:=1 to n do begin readln(w[i],v[i]);
    if v[i]>max then max:=v[i];end;
    for i:=1 to m do readln(a[i],b[i]);
    l:=1; r:=max; mid:=(l+r)shr 1;
    repeat
    tot2:=0;
    fillchar(c,sizeof(c),false);
    fillchar(d,sizeof(d),0);
    fillchar(e,sizeof(e),0);
    for i:=1 to n do
    if w[i]>=mid then c[i]:=true;
    for i:=1 to n do if c[i] then
    begin d[i]:=d[i-1]+1;e[i]:=e[i-1]+v[i];end
    else begin d[i]:=d[i-1];e[i]:=e[i-1];end;
    for i:=1 to m do
    tot2:=tot2+(d[b[i]]-d[a[i]-1])*(e[b[i]]-e[a[i]-1]);
    if abs(tot2-s)<ans then ans:=abs(tot2-s);
    if tot2<s then begin r:=mid-1;mid:=(l+r)shr 1;end;
    if tot2>s then begin l:=mid+1;mid:=(l+r)shr 1;end;
    if tot2=s then begin writeln(0);halt;end;
    until r<l;
    writeln(ans);
    end.

    1:给ans赋值成1 shl 32 40分
    2:用了while循环 65分
    3: AC

  • 0
    @ 2014-11-06 19:33:47

    二分答案然后前缀和计算检验值。

  • 0
    @ 2013-10-26 22:46:03

    var
    n,m,s,i,mid,t:longint;
    minans,tt,ss:int64;
    w,v,l,r,sum,tot:Array[0..200000]of int64;
    function check(mid:longint):int64;
    var i:longint;
    begin
    for i:=1 to n do
    if w[i]>=mid then begin tot[i]:=tot[i-1]+1; sum[i]:=sum[i-1]+v[i]; end
    else begin tot[i]:=tot[i-1]; sum[i]:=sum[i-1]; end;
    check:=0;
    for i:=1 to m do
    inc(check,(tot[r[i]]-tot[l[i]-1])*(sum[r[i]]-sum[l[i]-1]));
    end;
    begin
    assign(input,'qc.in');
    assign(output,'qc.out');
    reset(input); rewrite(output);
    readln(n,m,ss);
    for i:=1 to n do readln(w[i],v[i]);
    for i:=1 to m do readln(l[i],r[i]);
    s:=0; t:=1000000; minans:=1<<62;
    while s<t do
    begin
    mid:=(s+t)>>1;
    tt:=check(mid);
    if abs(ss-tt)<minans then minans:=abs(ss-tt);
    if tt<ss then t:=mid-1 else s:=mid+1;
    end;
    tt:=check(s);
    if abs(ss-tt)<minans then minans:=abs(ss-tt);
    writeln(minans);
    close(input); close(output);
    end.

  • 0
    @ 2013-08-07 17:52:18

    =.= 忘了int64
    Var n,m,i,j:longint;
    s,ans,left,right,mid:int64;
    w,v,f,sum,l,r:array[0..200000] of longint;
    Function min(a,b:int64):int64;
    Begin
    If a<b then exit(a) else exit(b);
    End;
    Procedure inity(minw:longint);
    Var i:longint;
    Begin
    fillchar(f,sizeof(f),0);
    fillchar(sum,sizeof(sum),0);
    For i:=1 to n do
    Begin
    f[i]:=f[i-1];
    sum[i]:=sum[i-1];
    If w[i]>=minw then
    Begin
    inc(f[i]);
    sum[i]:=sum[i]+v[i];
    End;
    End;
    End;
    Procedure init;
    Var i,j:longint;
    Begin
    assign(input,'qc.in');
    reset(input);
    Readln(n,m,s);
    For i:=1 to n do readln(w[i],v[i]);
    For i:=1 to m do readln(l[i],r[i]);
    End;
    Function work(minw:longint):int64;
    Var i,j:longint;
    y:int64;
    Begin
    y:=0;
    inity(minw);
    For i:=1 to m do
    y:=y+(f[r[i]]-f[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
    work:=y;
    End;
    Procedure main;
    Var i:longint;
    Begin
    left:=1; right:=1000000000;
    while left+1<right do
    begin
    mid:=(left+right)div 2;
    ans:=work(mid);
    if ans>s then left:=mid
    else right:=mid;
    end;
    writeln(min(abs(work(right)-s),abs(work(left)-s)));
    End;
    Begin
    init;
    main;
    End.

  • 0
    @ 2013-03-10 10:06:58

    var i,j,l,n,m:longint;
    r,s,mid,ans,y:int64;
    legal,sum,w,v:array[0..300000] of int64;
    left,right:array[0..300000] of longint;

    procedure setlegal(ww:longint);
    var i,j:longint;
    begin
    for i:=1 to n do if w[i]>=ww then legal[i]:=legal[i-1]+1 else legal[i]:=legal[i-1];
    end;

    procedure setsum(ww:longint);
    var i,j:longint;
    begin
    for i:=1 to n do if w[i]>=ww then sum[i]:=sum[i-1]+v[i] else sum[i]:=sum[i-1];
    end;

    begin
    read(n,m,s);
    for i:=1 to n do begin read(w[i],v[i]); if w[i]>r then r:=w[i];end;
    for i:=1 to m do read(left[i],right[i]);
    ans:=maxlongint*100;
    l:=1;
    while l<=r do
    begin
    mid:=(l+r)>>1;
    setlegal(mid);
    setsum(mid);
    y:=0;
    for i:=1 to m do
    y:=y+(legal[right[i]]-legal[left[i]-1])*(sum[right[i]]-sum[left[i]-1]);
    if ans>abs(y-s) then ans:=abs(y-s);
    if y>s then l:=mid+1;
    if y<s then r:=mid-1;
    if l+1=r then break;
    if y=s then break;
    end;
    writeln(ans);
    end.

  • 0
    @ 2012-10-24 16:00:12

    program happy;

    var m,n,i,x,ll,rr,mm,max:longint;

        w,v,l,r:array[0..200100]of longint;

        ans,s,y:int64;

        t,vv:array[0..200100]of int64; //用数组计数避免重复计算

    procedure tryy(k:longint);

    var i,j:longint;

    begin

     y:=0;

     for i:=1 to n do

     begin

      t[i]:=t;vv[i]:=vv;

      if w[i]>=k then

      begin

       t[i]:=t[i]+1;vv[i]:=vv[i]+v[i];

      end;

     end;

     for i:=1 to m do

     y:=y+(t[r[i]]-t[l[i]-1])*(vv[r[i]]-vv[l[i]-1]);

    end;

    begin

     readln(n,m,s);

     max:=0;

     for i:=1 to n do

     begin

      readln(w[i],v[i]);

      if w[i]>max then max:=w[i];

     end;

     for i:=1 to m do readln(l[i],r[i]);

     ans:=10000000000000000;

     ll:=0; rr:=max;

     repeat

      mm:=(ll+rr)shr 1;      //二分答案

      tryy(mm);

      if abs(y-s)

    • @ 2015-07-08 09:48:01

      一开始不懂二分,这个程序我一看就明白了,十分感谢

  • 0
    @ 2012-10-23 20:32:43

    test

  • 0
    @ 2012-10-22 21:36:41

    var

    w,v,a,b,l,r:array[0..200000]of longint;

    c:array[0..200000]of int64;

    n,m,i,st,mid,en:longint;

    k,uu:int64;

    function min(x,y:int64):int64;

    begin

    if x=k then st:=mid+1 else en:=mid;

    end;

    if st=1 then writeln(k-deal(a[1],2))

    else if deal(a[st],2)>=k then writeln(deal(a[st],2)-k)

    else writeln(min(k-deal(a[st],2),deal(a[st-1],2)-k));

    close(input);

    close(output);

    end.

信息

ID
1740
难度
7
分类
其他 | 二分查找 点击显示
标签
递交数
4083
已通过
851
通过率
21%
被复制
14
上传者