【Codeforces 140C】New Year Snowmen

【链接】 我是链接,点我呀:)

【题意】

题意

【题解】

每次都选择剩余个数最多的3个不同数字组成一组.
优先消耗剩余个数多的数字
这样能尽量让剩余的数字总数比较多,从而更加可能得到更多的3个组合

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

int n;

map<int,int> dic;

priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > > pq;

vector<pair<int,pair<int,int> > > ans;

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

    for (int i = 1;i <= n;i++) {

        int x;

        cin >> x;

        dic[x]++;

    }

    for (pair<int,int> temp:dic){

        pq.push(make_pair(temp.second,temp.first));

    }

    while ((int)pq.size()>=3){

        pair<int,int> temp1 = pq.top();pq.pop();

        pair<int,int> temp2 = pq.top();pq.pop();

        pair<int,int> temp3 = pq.top();pq.pop();

        if (temp1.second<temp2.second) swap(temp1,temp2);

        if (temp1.second<temp3.second) swap(temp1,temp3);

        if (temp2.second<temp3.second) swap(temp2,temp3);

        ans.push_back(make_pair(temp1.second,make_pair(temp2.second,temp3.second)));

        temp1.first--;

        if (temp1.first>0) pq.push(temp1);

        temp2.first--;

        if (temp2.first>0) pq.push(temp2);

        temp3.first--;

        if (temp3.first>0) pq.push(temp3);

    }

    cout<<(int)ans.size()<<endl;

    for (int i = 0;i < (int)ans.size();i++){

        cout<<ans[i].first<<" "<<ans[i].second.first<<" "<<ans[i].second.second<<endl;

    }

	return 0;

}