题意翻译
现在来做雪人,每个雪人由三个不同大小的雪球构成:一个大的,一个中等的,一个小的。
现在有$n$个雪球半径分别为$r_1, r_2, …, r_n$
为了做雪人,三个雪球的大小必须两两不同。例如,半径分别为 $1,2,3$ 的雪球可以做成雪人,但$2,2,3$或$2,2,2$就不行。请帮忙计算最多能做出的雪人数量。
输入格式
第一行是一个整数$n$,代表雪球的数量.
接下来一行有n个整数$r_1,r_2……r_i$,分别代表每个雪球的半径。
输出格式
共$k + 1$行
第一行是一个数$k$,表示最大的雪人数.
接下来$k$行是每个雪人的描述,每行三个数,分别代表大雪球的半径,中等雪球的半径,小雪球的半径.
允许按任意顺序输出雪人描述. 如果有多种方案,输出任意一个
Output ‘s eg 1
Output ‘s eg 2
数据范围和约定
对于$100\%$的数据,保证$0 < n < 10^5$,$0 < r_i < 10^9$
分析
一道贪心好题。
考虑一种很显然的贪心:每一次取出出现次数最多的三种雪球。
由于数据大小高达$10^9$,因此,我们先对数据进行离散化。
之后使用优先队列维护雪球数量,每一次取出堆顶的$3$个元素,然后分别-1
。如果还有剩余的雪球,就再次放入堆中。
时间复杂度$O(nlogn)$,足以跑过$10^5$的数据。
剩下的详见代码注释。
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; }
|
后记
没错,这又是一道提交了很多次的题目。
![New Year Snowman.png](/img/loading.gif)
其中大部分错误还都是zz错误,包括忘记离散化,排序时仅排了一个数组,输出前不排序等……
因此,这又是一个提升的机会。
希望下次不要再犯这种zz错误了……
THE END