M_sea

CF140C New Year Snowmen
CodeForcesLuogu分析考虑一个显而易见的贪心:每次取出三种出现次数最多的雪球。这个正确性是显然的,然而...
扫描右侧二维码阅读全文
20
2018/12

CF140C New Year Snowmen

CodeForces

Luogu

分析

考虑一个显而易见的贪心:每次取出三种出现次数最多的雪球。

这个正确性是显然的,然而我并不会证。

然后就可以用堆来维护每种雪球。

若该种雪球取走一个后还能取,就把它再丢回堆里。

细节见代码。

代码

Luogu最优解。

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

struct Snowball {
    int r,s;
    bool operator <(const Snowball& rhs) const {
        return s<rhs.s; //s大的先出堆
    }
} a[MAXN];
priority_queue<Snowball> Q;

int b[MAXN];
int Ansa[MAXN],Ansb[MAXN],Ansc[MAXN];

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) b[i]=read();
    stable_sort(b+1,b+n+1);
    int tot=0;
    for (re int i=1;i<=n;++i) {
        if (b[i]!=b[i-1]) a[++tot].r=b[i],a[tot].s=1;
        else ++a[tot].s;
    }
    for (re int i=1;i<=tot;++i) Q.push(a[i]);
    int ans=0;
    while (Q.size()>=3) {
        Snowball x=Q.top(); Q.pop();
        Snowball y=Q.top(); Q.pop();
        Snowball z=Q.top(); Q.pop();
        ++ans,--x.s,--y.s,--z.s;
        Ansa[ans]=x.r,Ansb[ans]=y.r,Ansc[ans]=z.r;
        if (x.s) Q.push(x);
        if (y.s) Q.push(y);
        if (z.s) Q.push(z);
    }
    printf("%d\n",ans);
    for (re int i=1;i<=ans;++i) {
        if (Ansa[i]<Ansb[i]) swap(Ansa[i],Ansb[i]);
        if (Ansa[i]<Ansc[i]) swap(Ansa[i],Ansc[i]);
        if (Ansb[i]<Ansc[i]) swap(Ansb[i],Ansc[i]);
        printf("%d %d %d\n",Ansa[i],Ansb[i],Ansc[i]);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 42 PM

发表评论