ZJT's Blog

Keep your determination.

集训队作业之ARC076-F

2017-11-22 8:432017-11-22 8:43
集训队作业AtCoder贪心优先队列

传送门

从前往后贪心一下,维护两个优先队列$S_1,S_2$,$S_1$存已经在$L_i$左边取了的,$S_2$存$L_i$左边已经满了,只能在$R_i$右边取的。先尽量取左端点靠前的,如果一个人取不了了,就看$S_1$里面有没有右端点比他的右端点小的,如果有就就把之前取的那个人换掉,这样就能保证$S_2$里面的右端点都尽可能小。如果已经没有人能从$L_i$左边取了,就从$S_2$里面右端点最小的开始取,直到位置占满或$S_2$空了为止。可以证明这样做是最优的。

写的时候又出了一点问题,就是我为了让priority_queue变成小根堆,直接存了每个值的相反数进去。结果我有一步是把一个堆的最小值扔进另一个堆,我又很傻逼地取了反再扔进去,盯了半天都没盯出来,随机数据又根本拍不出错。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 200010
using namespace std;

int n,m;
pair<int,int> a[MAXN];
priority_queue<int> S1,S2;

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].first,&a[i].second);
        a[i].second=-a[i].second;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) a[i].second=-a[i].second;
    int now=1;
    int ans=0;
    while(now<=n && a[now].first==0)
        S2.push(-a[now++].second);
    for(int i=1;i<=m;i++){
        if(now<=n){
            ans++;
            S1.push(-a[now++].second);
            while(now<=n && a[now].first==i){
                if(a[now].second>-S1.top()){
                    S2.push(S1.top());
                    S1.pop();
                    S1.push(-a[now].second);
                }else S2.push(-a[now].second);
                now++;
            }
        }else{
            if(!S2.empty() && -S2.top()<=i){
                S2.pop();
                ans++;
            }
        }
    }
    printf("%d\n",n-ans);
    return 0;
}

查看详细内容

集训队作业之ARC080-E

2017-10-9 10:292017-10-9 10:29
集训队作业AtCoderfhq Treap优先队列

传送门

为了字典序最小,我们考虑最终能插到队首的最小的数。显然这个数必须在奇数位,然后跟他一起插进去的另一个数应该是在他后面的一个偶数位的数。插完之后,整个序列会分成三段,每一段分别递归处理就行了。关于答案的处理,直接拿一个优先队列去维护当前能插的数就行了。

于是我们分别维护所有位于奇数位和偶数位的数,要实现一个数据结构,支持序列分割和序列取最小。然后想也没想就写了fhq treap。。。结果A掉之后看了看题解,发现直接维护区间在原序列中的位置+原序列中RMQ就行了。。。我说ARC的E怎么可能会考平衡树,真的是学数据结构学傻了。。。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define INF 0x77777777
#define MAXN 200010
using namespace std;

int n;
int p[MAXN];
pair<int,int> pt[MAXN];
int ch[MAXN][3],numpt;

namespace Treap{
    struct node{
        int lc,rc,size,key;
        int v,minv;
    }a[MAXN];

    void init(){
        for(int i=1;i<=n;i++){
            a[i].key=rand();
            a[i].v=a[i].minv=p[i];
            a[i].size=1;
        }
        a[0].v=a[0].minv=INF;
    }

    void pushup(int x){
        a[x].size=a[a[x].lc].size+a[a[x].rc].size+1;
        a[x].minv=min(min(a[a[x].lc].minv,a[a[x].rc].minv),a[x].v);
    }

    int merge(int x,int y){
        if(!x) return y;
        if(!y) return x;
        if(a[x].key<a[y].key){
            a[x].rc=merge(a[x].rc,y);
            pushup(x);
            return x;
        }else{
            a[y].lc=merge(x,a[y].lc);
            pushup(y);
            return y;
        }
    }

    pair<int,int> split(int x,int k){
        if(!x) return make_pair(0,0);
        if(k<=a[a[x].lc].size){
            pair<int,int> temp=split(a[x].lc,k);
            a[x].lc=temp.second;
            pushup(x);
            return make_pair(temp.first,x);
        }else{
            pair<int,int> temp=split(a[x].rc,k-a[a[x].lc].size-1);
            a[x].rc=temp.first;
            pushup(x);
            return make_pair(x,temp.second);
        }
    }

    int findmin(int x){
        if(a[x].v==a[x].minv) return a[a[x].lc].size+1;
        if(a[a[x].lc].minv<a[a[x].rc].minv) return findmin(a[x].lc);
        else return findmin(a[x].rc)+a[a[x].lc].size+1;
    }
}

int gao(int r1,int r2){
    using namespace Treap;
    if(!r1 || !r2) return 0;
    int minpos=findmin(r1);
    pair<int,int> t1=split(r1,minpos-1);
    pair<int,int> t2=split(t1.second,1);
    int pt1=t2.first;
    pair<int,int> t3=split(r2,minpos-1);
    int minpos2=findmin(t3.second);
    pair<int,int> t4=split(t3.second,minpos2-1);
    pair<int,int> t5=split(t4.second,1);
    int pt2=t5.first;
    pair<int,int> t6=split(t2.second,minpos2-1);
    int x=++numpt;
    pt[x]=make_pair(a[pt1].v,a[pt2].v);
    ch[x][0]=gao(t1.first,t3.first);
    ch[x][1]=gao(t4.first,t6.first);
    ch[x][2]=gao(t6.second,t5.second);
    return x;
}

void output(){
    static priority_queue< pair<int,int> > Q;
    Q.push(make_pair(-pt[1].first,1));
    while(!Q.empty()){
        int x=Q.top().second;
        Q.pop();
        printf("%d %d ",pt[x].first,pt[x].second);
        if(ch[x][0]) Q.push(make_pair(-pt[ch[x][0]].first,ch[x][0]));
        if(ch[x][1]) Q.push(make_pair(-pt[ch[x][1]].first,ch[x][1]));
        if(ch[x][2]) Q.push(make_pair(-pt[ch[x][2]].first,ch[x][2]));
    }
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",p+i);
    Treap::init();
    int r1=0,r2=0;
    for(int i=1;i<=n;i+=2){
        r1=Treap::merge(r1,i);
        r2=Treap::merge(r2,i+1);
    }
    gao(r1,r2);
    output();
    return 0;
}

查看详细内容