Hrbust 1176 小陈老师、雪人

小陈老师、雪人

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1176

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 79(22 users)

Total Accepted: 32(14 users)

Rating:

Special Judge: Yes

Description

东北的冬季，尤其是过年的时候，小陈老师喜欢去堆雪人。每个雪人主要由三个雪球构成：大雪球、中雪球、小雪球。他已经准备好了N个雪球，半径分别等于r1, r2, ..., rn。如果要堆一个雪人，就需要三个半径互不相等的雪球。例如：三个雪球的半径为1、2、3，能够用来堆一个雪人。但是半径为2、2、3或者2、2、2的三个雪球就不可以。快帮帮小陈老师，算算他最多能用这些雪球堆多少个雪人。

Input

对于每组测试数据：第1行，包含一个整数n(1≤n≤100000) — 雪球的数量。第2行，包含n个整数 — 雪球的半径r1, r2, ..., rn (1≤ri≤1000000000)。处理到文件结束

Output

对于每组测试数据：第1行，输出最多能堆多少雪人 - k。接下来k行，每行描述一个雪人，每行用空格分割三个数字分别表示大雪球、中雪球、小雪球的半径。可以用任何顺序输出每个雪人。如果有多种可行解，输出任意一个即可。

Sample Input

1 2 3 4 5 6 7

2 2 3

Sample Output

3 2 1

6 5 4

Author

齐达拉图

练习优先队列的使用，，，题意简单，找出有多少组不同的三个数组成的组数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>

using namespace std;

const int N=100010;

int n,res[N][3];

struct node{
    int x,num;
    bool operator < (const node &a) const{
        return a.num>num;
    }
};

void swap(int &a,int &b){
    int tmp=a;a=b;b=tmp;
}

int main(){

    //freopen("input.txt","r",stdin);

    priority_queue<node> q;
    map<int,int> mp;
    map<int,int>::iterator it;
    while(~scanf("%d",&n)){
        while(!q.empty())
            q.pop();
        mp.clear();
        int x;
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            mp[x]++;
        }
        node tmp;
        for(it=mp.begin();it!=mp.end();it++){
            tmp.x=(*it).first;
            tmp.num=(*it).second;
            //printf("%d %d\n",tmp.x,tmp.num);
            q.push(tmp);
        }
        int cnt=0,a1,a2,a3;
        node tmp1,tmp2,tmp3;
        while(!q.empty()){
            tmp1=q.top();
            q.pop();
            a1=tmp1.x;
            tmp1.num--;
            if(q.empty())
                break;

            tmp2=q.top();
            q.pop();
            a2=tmp2.x;
            tmp2.num--;
            if(q.empty())
                break;

            tmp3=q.top();
            q.pop();
            a3=tmp3.x;
            tmp3.num--;

            if(tmp1.num>0)
                q.push(tmp1);
            if(tmp2.num>0)
                q.push(tmp2);
            if(tmp3.num>0)
                q.push(tmp3);

            if(a1<a2)
                swap(a1,a2);
            if(a1<a3)
                swap(a1,a3);
            if(a2<a3)
                swap(a2,a3);
            res[cnt][0]=a1, res[cnt][1]=a2, res[cnt++][2]=a3;
        }
        printf("%d\n",cnt);
        for(int i=0;i<cnt;i++)
            printf("%d %d %d\n",res[i][0],res[i][1],res[i][2]);
    }
    return 0;
}