0%

Codeforces Round #100 C. New Year Snowmen

题目链接:http://codeforces.com/problemset/problem/140/C

  • 这个题是我们有次小比赛的题,当时脑子比较乱,写了一堆bug,今天想了起来就补了一下题。

这题就是在处理数据稍微麻烦了点,因为数据范围是1e8,用数组去记录每个值的个数显然是不可能了,于是我用了一个unordered_map来映射每个值出现的次数,然后放到一个按照值的个数排序的优先队列中,优先取出来个数比较多的。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<map>
#include<unordered_map>
using namespace std;
struct node{
int val,cnt;
node(int val,int cnt):val(val),cnt(cnt){}
bool operator < (const node & x)const{
return cnt<x.cnt;
}
};
struct ans{
int a;int b;int c;
ans(int a,int b,int c):a(a),b(b),c(c){}
};
priority_queue<node>pq;
queue<ans>qu;
unordered_map<int,int>umap;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
while(!pq.empty()) pq.pop();
while(!qu.empty()) pq.pop();
int r;
while(n--){
cin>>r;
umap[r]++;
}
unordered_map<int,int>::iterator it;
for(it=umap.begin();it!=umap.end();it++){
pq.push(node(it->first,it->second));
}
while(pq.size()>2){
node a=pq.top();pq.pop();a.cnt--;
node b=pq.top();pq.pop();b.cnt--;
node c=pq.top();pq.pop();c.cnt--;
int cur[3]={a.val,b.val,c.val};
sort(cur,cur+3);
qu.push(ans(cur[2],cur[1],cur[0]));
if(a.cnt>0) pq.push(a);
if(b.cnt>0) pq.push(b);
if(c.cnt>0) pq.push(c);
}
cout<<qu.size()<<endl;
while(!qu.empty()){
ans tmp=qu.front();
qu.pop();
cout<<tmp.a<<" "<<tmp.b<<" "<<tmp.c<<endl;
}

return 0;
}
如果对您有帮助,请我喝杯奶茶?