CodeForces #100 C 贪心+STL

题目链接:CodeForces #100  C

题意:现在给出n个snowball的半径,3个半径严格递增或递减的snowball,可以组成1个snowmen。问最多能组成多少个snowmen。并且按照半径递减的顺序输出每个snowmen的组成。

思路:嗯...每次都从前三个个数最多的snowball里选择,最后组成的snowmen最多...

...可以用优先队列写..但是感觉set+map写的太优雅了...map当然不等于数组了...哼。

#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std; typedef pair<int, int> pair_;
map<int, int> mp;
set<pair_> st;
vector<int> ans; int main() {
//freopen("in.cpp", "r", stdin);
int n;
while(~scanf("%d", &n)) {
mp.clear();
st.clear();
ans.clear();
int temp;
for (int i=0; i<n; ++i) {
scanf("%d", &temp);
mp[temp]++;
}
map<int, int>::iterator mpit;
for (mpit = mp.begin(); mpit != mp.end(); ++mpit) {
//st.insert(pair_((*mpit).second, (*mpit).first));
st.insert(pair_(mpit->second, mpit->first));
}
while(st.size() >= 3) {
pair_ now[3];
for (int i=0; i<3; ++i) {
now[i] = *--st.end();
st.erase(--st.end());
ans.push_back(now[i].second);
}
for (int i=0; i<3; ++i) {
if (--now[i].first) st.insert(now[i]);
}
sort(ans.rbegin(),ans.rbegin()+3);
}
printf("%d\n", ans.size()/3);
for (int i=0; i<ans.size(); i+=3) {
printf("%d %d %d\n", ans[i], ans[i+1], ans[i+2]);
}
}
return 0;
}
上一篇:Windows系统和Linux系统安装JDK8详细教程


下一篇:linux下jdk8安装