题意翻译

现在来做雪人，每个雪人由三个不同大小的雪球构成：一个大的，一个中等的，一个小的。

现在有个雪球半径分别为

​为了做雪人，三个雪球的大小必须两两不同。例如，半径分别为 的雪球可以做成雪人，但或就不行。请帮忙计算最多能做出的雪人数量。

输入格式

第一行是一个整数，代表雪球的数量.

接下来一行有n个整数，分别代表每个雪球的半径。

输出格式

共行

第一行是一个数,表示最大的雪人数.

接下来行是每个雪人的描述，每行三个数，分别代表大雪球的半径，中等雪球的半径，小雪球的半径.

允许按任意顺序输出雪人描述. 如果有多种方案，输出任意一个

Input & Output 's examples

Input 's eg 1

7
1 2 3 4 5 6 7

Output 's eg 1

2
3 2 1
6 5 4

Input 's eg 2

3
2 2 3

Output 's eg 2

0

数据范围和约定

对于的数据，保证，

分析

一道贪心好题。

考虑一种很显然的贪心：每一次取出出现次数最多的三种雪球。

由于数据大小高达，因此，我们先对数据进行离散化。

之后使用优先队列维护雪球数量，每一次取出堆顶的个元素，然后分别-1。如果还有剩余的雪球，就再次放入堆中。

时间复杂度，足以跑过的数据。

剩下的详见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

struct Ball{
    int id;
    int number;
    bool operator < (const Ball &b) const{
        return number < b.number;
    }
}ball[N];

int n;
int a[N] , b[N];
int ans_x[N] , ans_y[N] , ans_z[N];

priority_queue<Ball > Q;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(a + 1 , a + 1 + n);
    sort(b + 1 , b + 1 + n);
    int len = unique(b + 1 , b + 1 + n) - b - 1;
    for(int i = 1; i <= n;){        //离散化数据
        int j = i;
        while(j + 1 <= n && a[j + 1] == a[i]){
            j ++;
        }
        int finish = j - i + 1;
        int num = lower_bound(b + 1 , b + 1 + len , a[i]) - b; 
        Q.push((Ball){num , finish});
        i = j + 1;
    }
    int ans = 0;
    while(Q.size() >= 3){       
        Ball x = Q.top();       //取出堆顶的元素
        Q.pop();
        Ball y = Q.top();
        Q.pop();
        Ball z = Q.top();
        Q.pop();
        x.number --;        
        if(x.number > 0){       //如果还有剩下的雪球，就放回堆中。
            Q.push((Ball){x.id , x.number});
        }
        y.number --;
        if(y.number > 0){
            Q.push((Ball){y.id , y.number});
        }
        z.number --; 
        if(z.number > 0){
            Q.push((Ball){z.id , z.number});
        }
        ans ++;
        ans_x[ans] = b[x.id];
        ans_y[ans] = b[y.id];      //统计答案
        ans_z[ans] = b[z.id];
    }
    cout << ans << "\n";
    for (int i = 1; i <= ans; i ++){
        int tt[3];      
        tt[0] = ans_x[i], tt[1] = ans_y[i], tt[2] = ans_z[i];
        sort(tt, tt + 3);       //输出前排序
        printf("%d %d %d\n", tt[2], tt[1], tt[0]);
    }
    return 0;
}

后记

没错，这又是一道提交了很多次的题目。

其中大部分错误还都是zz错误，包括忘记离散化，排序时仅排了一个数组，输出前不排序等……

因此，这又是一个提升的机会。

希望下次不要再犯这种zz错误了……

THE END