CF140C New Year Snowmen

发布于 2019-11-05  110 次阅读


Link

一道堆的好题。

一看到题我先考虑的了DP,但是你看这个配对问题好像并不需要DP并且DP也不好处理。再观察构成雪人的条件是 r_1 < r_2 < r_3,就可以往用堆处理数据再贪心地选这方面的想。

具体的,我们可以把 r_i 按照降序排序,相同半径的雪人球我们可以另开一个结构体存储,并且对于同一半径的雪人球我们要对他们统计数量。之后把这些去完重并且统计好数量的雪人球压进一个堆里,按照数量排序。

接下来我们每次取三个最多的雪人球,记为答案,如果这一半径的雪人球还有,我们就再次压进堆里。

就是这样。

证明可看我校神仙神tst的Blog,如有不懂可看上楼M_sea小姐姐和撤云的题解,也可以私信。

上代码

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100000 + 5;

int n;
int b[SIZE], ansa[SIZE], ansb[SIZE], ansc[SIZE];

struct node
{
    int r, sum;
    inline bool operator < (const node &a) const {
        return sum < a.sum;
    }
} a[SIZE];

std::priority_queue < node > Q;

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

int main()
{
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++) 
        b[i] = read();
    std::sort(b + 1, b + n + 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] != b[i - 1]) a[++cnt].r = b[i], a[cnt].sum = 1;
        else a[cnt].sum++;
    }
    for (int i = 1; i <= cnt; i++) Q.push(a[i]);
    int ans = 0;
    while (Q.size() >= 3) {
        node x = Q.top(); Q.pop();
        node y = Q.top(); Q.pop();
        node z = Q.top(); Q.pop();
        ++ans, --x.sum, --y.sum, --z.sum;
        ansa[ans] = x.r, ansb[ans] = y.r, ansc[ans] = z.r;
        if (x.sum) Q.push(x); if (y.sum) Q.push(y); if (z.sum) Q.push(z);
    }
    printf("%d\n", ans);
    for (int i = 1; i <= ans; i++) {
        if (ansa[i] < ansb[i]) std::swap(ansa[i], ansb[i]);
        if (ansa[i] < ansc[i]) std::swap(ansa[i], ansc[i]);
        if (ansb[i] < ansc[i]) std::swap(ansb[i], ansc[i]);
        printf("%d %d %d\n", ansa[i], ansb[i], ansc[i]);
    }
    return 0;
}

苟利国家生死以,岂因祸福避趋之.