0分代码，求DALAO帮忙看一下（我好弱啊）

P4064 [JXOI2017] 加法

karl @ 2019-07-23 15:08:07

include <algorithm>

include <iostream>

include <cstdlib>

include <cstring>

include <cstdio>

include <vector>

include <cmath>

include <ctime>

include <queue>

include <set>

include <map>

using namespace std;

define MAX 1e9+7

struct segment{ int l; int r; }; segment seg[200020]; int n,m,k,A,T,a[200020],L,R,mid,vis[200020],k1,ans,heap[200020],tot; bool cmp(segment x,segment y){ if(x.l==y.l) return x.r<x.r; return x.l<y.l; } void insert(int x){ if(x==1) return ; int k1; if(heap[x]>heap[x/2]){ k1=heap[x]; heap[x]=heap[x/2]; heap[x/2]=k1; insert(x/2); } return ; } void change(int x){ int k1=x2; int k2=x2+1; int k3; if(k1>tot&&k2>tot){ return ; } if(heap[k1]>heap[k2]||k2>tot){ if(heap[x]<heap[k1]){ k3=heap[x]; heap[x]=heap[k1]; heap[k1]=k3; change(k1); } } else{ if(heap[x]<heap[k2]){ k3=heap[x]; heap[x]=heap[k2]; heap[k2]=k3; change(k2); } } return ; } int check(int x){ tot=0; int line=0; int dif[200020]; int d=0; int k1,k2; for(int i=1;i<=n;i++){ dif[i]=0; heap[i]=0; } for(int i=1;i<=n;i++){ if(i>=seg[line+1].l){ tot++; line++; heap[tot]=seg[line].r; insert(tot); } d+=dif[i]; k1=a[i]+dA; while(k1<x&&tot!=0){ k2=heap[1]; if(k2<i) return 0; heap[1]=heap[tot]; heap[tot]=0; tot--; change(1); k1+=A; d++; dif[k2+1]--; } if(k1<x) return 0; } return 1; } int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); scanf("%d",&T); while(T--){ k1=MAX; scanf("%d%d%d%d",&n,&m,&k,&A); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); k1=min(k1,a[i]); } for(int i=1;i<=m;i++) scanf("%d%d",&seg[i].l,&seg[i].r); sort(seg+1,seg+m+1,cmp); L=k1; R=k1+kA; k1=0; while(L<=R){ mid=(L+R)/2; if(L==R){ ans=L; break; } if(check(mid)==1){ L=mid+1; } else R=mid; } printf("%d\n",ans); } return 0; }

by karl @ 2019-07-23 15:09:44

～～～

include <algorithm>

include <iostream>

include <cstdlib>

include <cstring>

include <cstdio>

include <vector>

include <cmath>

include <ctime>

include <queue>

include <set>

include <map>

using namespace std;

define MAX 1e9+7

struct segment{ int l; int r; }; segment seg[200020]; int n,m,k,A,T,a[200020],L,R,mid,vis[200020],k1,ans,heap[200020],tot; bool cmp(segment x,segment y){ if(x.l==y.l) return x.r<x.r; return x.l<y.l; } void insert(int x){ if(x==1) return ; int k1; if(heap[x]>heap[x/2]){ k1=heap[x]; heap[x]=heap[x/2]; heap[x/2]=k1; insert(x/2); } return ; } void change(int x){ int k1=x2; int k2=x2+1; int k3; if(k1>tot&&k2>tot){ return ; } if(heap[k1]>heap[k2]||k2>tot){ if(heap[x]<heap[k1]){ k3=heap[x]; heap[x]=heap[k1]; heap[k1]=k3; change(k1); } } else{ if(heap[x]<heap[k2]){ k3=heap[x]; heap[x]=heap[k2]; heap[k2]=k3; change(k2); } } return ; } int check(int x){ tot=0; int line=0; int dif[200020]; int d=0; int k1,k2; for(int i=1;i<=n;i++){ dif[i]=0; heap[i]=0; } for(int i=1;i<=n;i++){ if(i>=seg[line+1].l){ tot++; line++; heap[tot]=seg[line].r; insert(tot); } d+=dif[i]; k1=a[i]+dA; while(k1<x&&tot!=0){ k2=heap[1]; if(k2<i) return 0; heap[1]=heap[tot]; heap[tot]=0; tot--; change(1); k1+=A; d++; dif[k2+1]--; } if(k1<x) return 0; } return 1; } int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); scanf("%d",&T); while(T--){ k1=MAX; scanf("%d%d%d%d",&n,&m,&k,&A); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); k1=min(k1,a[i]); } for(int i=1;i<=m;i++) scanf("%d%d",&seg[i].l,&seg[i].r); sort(seg+1,seg+m+1,cmp); L=k1; R=k1+kA; k1=0; while(L<=R){ mid=(L+R)/2; if(L==R){ ans=L; break; } if(check(mid)==1){ L=mid+1; } else R=mid; } printf("%d\n",ans); } return 0; } ～～～

by karl @ 2019-07-23 15:10:22

我甚至连MARKDOWN都不会用。。。

by karl @ 2019-07-23 15:12:10

<pre>

include <algorithm>

include <iostream>

include <cstdlib>

include <cstring>

include <cstdio>

include <vector>

include <cmath>

include <ctime>

include <queue>

include <set>

include <map>

using namespace std;

define MAX 1e9+7

struct segment{ int l; int r; }; segment seg[200020]; int n,m,k,A,T,a[200020],L,R,mid,vis[200020],k1,ans,heap[200020],tot; bool cmp(segment x,segment y){ if(x.l==y.l) return x.r<x.r; return x.l<y.l; } void insert(int x){ if(x==1) return ; int k1; if(heap[x]>heap[x/2]){ k1=heap[x]; heap[x]=heap[x/2]; heap[x/2]=k1; insert(x/2); } return ; } void change(int x){ int k1=x2; int k2=x2+1; int k3; if(k1>tot&&k2>tot){ return ; } if(heap[k1]>heap[k2]||k2>tot){ if(heap[x]<heap[k1]){ k3=heap[x]; heap[x]=heap[k1]; heap[k1]=k3; change(k1); } } else{ if(heap[x]<heap[k2]){ k3=heap[x]; heap[x]=heap[k2]; heap[k2]=k3; change(k2); } } return ; } int check(int x){ tot=0; int line=0; int dif[200020]; int d=0; int k1,k2; for(int i=1;i<=n;i++){ dif[i]=0; heap[i]=0; } for(int i=1;i<=n;i++){ if(i>=seg[line+1].l){ tot++; line++; heap[tot]=seg[line].r; insert(tot); } d+=dif[i]; k1=a[i]+dA; while(k1<x&&tot!=0){ k2=heap[1]; if(k2<i) return 0; heap[1]=heap[tot]; heap[tot]=0; tot--; change(1); k1+=A; d++; dif[k2+1]--; } if(k1<x) return 0; } return 1; } int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); scanf("%d",&T); while(T--){ k1=MAX; scanf("%d%d%d%d",&n,&m,&k,&A); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); k1=min(k1,a[i]); } for(int i=1;i<=m;i++) scanf("%d%d",&seg[i].l,&seg[i].r); sort(seg+1,seg+m+1,cmp); L=k1; R=k1+kA; k1=0; while(L<=R){ mid=(L+R)/2; if(L==R){ ans=L; break; } if(check(mid)==1){ L=mid+1; } else R=mid; } printf("%d\n",ans); } return 0; } <code>

by yurzhang @ 2019-07-23 15:15:07

希望更丰富的展现？使用Markdown

by ⚡current⚡ @ 2019-07-23 15:20:27

希望更丰富的展现？使用Markdown

by karl @ 2019-07-23 15:23:04

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MAX 1e9+7
struct segment{
    int l;
    int r;
};
segment seg[200020];
int n,m,k,A,T,a[200020],L,R,mid,vis[200020],k1,ans,heap[200020],tot;
bool cmp(segment x,segment y){
    if(x.l==y.l) return x.r<x.r;
    return x.l<y.l;
}
void insert(int x){
    if(x==1) return ;
    int k1;
    if(heap[x]>heap[x/2]){
        k1=heap[x];
        heap[x]=heap[x/2];
        heap[x/2]=k1;
        insert(x/2);
    }
    return ;
}
void change(int x){
    int k1=x*2;
    int k2=x*2+1;
    int k3;
    if(k1>tot&&k2>tot){
        return ;
    }
    if(heap[k1]>heap[k2]||k2>tot){
        if(heap[x]<heap[k1]){
            k3=heap[x];
            heap[x]=heap[k1];
            heap[k1]=k3;
            change(k1);
        }
    }
    else{
        if(heap[x]<heap[k2]){
            k3=heap[x];
            heap[x]=heap[k2];
            heap[k2]=k3;
            change(k2);
        }
    }
    return ;
}
int check(int x){
    tot=0;
    int line=0;
    int dif[200020];
    int d=0;
    int k1,k2;
    int K=k;
    for(int i=1;i<=n;i++){
        dif[i]=0;
        heap[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(i>=seg[line+1].l){
            tot++;
            line++;
            heap[tot]=seg[line].r;
            insert(tot);
        }
        d+=dif[i];
        k1=a[i]+d*A;
        while(k1<x&&tot!=0&&K>0){
            k2=heap[1];
            K--;
            if(k2<i) return 0;
            heap[1]=heap[tot];
            heap[tot]=0;
            tot--;
            change(1);
            k1+=A;
            d++;
            dif[k2+1]--;
        }
        if(k1<x) return 0;
    }
    return 1;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d",&T);
    while(T--){
        k1=MAX;
        scanf("%d%d%d%d",&n,&m,&k,&A);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            k1=min(k1,a[i]);
        }
        for(int i=1;i<=m;i++) scanf("%d%d",&seg[i].l,&seg[i].r);
        sort(seg+1,seg+m+1,cmp);
        L=k1;
        R=k1+k*A;
        k1=0;
        while(L<=R){
            mid=(L+R)/2;
            if(L==R){
                ans=L;
                break;
            }
            if(check(mid)==1){
                L=mid+1;
            }
            else R=mid;
        }
        printf("%d\n",ans);
    }
    return 0;
}

by karl @ 2019-07-23 15:23:19

终于学会了。。。。

by karl @ 2019-07-24 08:57:03

我查了一下，堆的部分没有问题，其他的查不出来啊

|