题干：

 

浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁.

Input输入包含多组测试用例. 
每个用例首先包含2个整数n（0<n<=100000）和m(0<m<=10)，其中: n为镇上的人数，m为需要找出的大富翁数, 接下来一行输入镇上n个人的财富值. 
n和m同时为0时表示输入结束.Output请输出乌镇前m个大富翁的财产数，财产多的排前面，如果大富翁不足m个，则全部输出,每组输出占一行.Sample Input

3 1
2 5 -1
5 3
1 2 3 4 5
0 0

Sample Output

5
5 4 3

 

解题报告：水题，排序即可，优先队列亦可解。

 

 

排序ac：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int a[100000+5];
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m)) {
		if(n==0&&m==0) break;
		
		memset(a,0,sizeof(a));
		for(int i = 1; i<=n; i++) {
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1, greater<int>() );
		if(n<=m) {
			for(int i = 1; i<=n; i++) {
				printf("%d%c",a[i],i==n?'\n':' '); 
			}
			continue;
		}
		if(n>m) {
			for(int i = 1; i<= m; i++) {
				printf("%d%c",a[i],i==m?'\n':' '); 
			}
		}
	}
	return 0 ;
}

事实证明不加if(n<=m)的情况 也能ac，看来是样例中没出这样的样例？不然依照题干应该是有这一种情况发生啊。

 

优先队列ac：

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,less<int> >q;//等价于priority_queue<int> q;  从大到小排序 
int main()
{
	int n,t,a;
	while(scanf("%d %d",&n,&t)&&(n!=0||t!=0))
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a);
			q.push(a);
		}
			for(int i=0;i<t-1;i++)
			{
			printf("%d ",q.top());
			q.pop();
		    }
		    printf("%d",q.top());//最有一个数字没有空格。
		    printf("\n");
                    //每次别忘清空队列
		    while(!q.empty())  q.pop();
	}
	return 0;
}
	int n,t,a;
	while(scanf("%d %d",&n,&t)&&(n!=0||t!=0))
	{
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a);
			q.push(a);
		}
			for(int i=0;i<t-1;i++)
			{
			printf("%d ",q.top());
			q.pop();
		    }
		    printf("%d",q.top());//最有一个数字没有空格。
		    printf("\n");
                    //每次别忘清空队列
		    while(!q.empty())  q.pop();
	}
	return 0;
}

优先队列ac2：（优化了n<=m的情况）源自网络

/*
当输入小于m个的时候，一直输入，当输入大于m个数之后 ，这m个数会按照从小到大的顺序排序，
再往里面输入的时候要进行判断，如果那个数比对顶元素大的话，这个数进队，对顶元素出对，
进队后就又变成从小到大排序了，输入完毕之后，将数据按从大到小输出，因为对顶元素是最小值，
所以，应该将元素 都重新赋值到数组中，然后从后往前输出！（就这个转换方法必须想到！！！）
*/
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int a,b[100005];
int main() {
	int n,m,i,j,k;
	while(scanf("%d%d",&n,&m)&&(n||m)) { //n,m分别代表村中的总人数，和最富有的前m个人
		for(i=0; i<n; i++) { //将财产值放到队列中
			scanf("%d",&a);
			if(q.size()<m)
				q.push(a);
			else if(a>q.top()) {
				q.push(a);
				q.pop();
			}
		}
		if(n>m) { //当总人数比富翁人数多的话执行下面语句
			for(i=0; i<m; i++) {
				b[i]=q.top();
				q.pop();
			}
			for(i=m-1; i>0; i--)
				printf("%d ",b[i]);
			printf("%d\n",b[0]);
		} else { //总人数没有富翁人数多的话，执行这个下面的语句！
			for(i=0; i<n; i++) {
				b[i]=q.top();
				q.pop();
			}
			for(i=n-1; i>0; i--)
				printf("%d ",b[i]);
			printf("%d\n",b[0]);
		}
	}
	return 0;
}

今天又用set实现了一下，，第一发错了，后来发现需要multiset

AC代码：

#include<bits/stdc++.h>

using namespace std;
multiset<int,greater<int> > ss;
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m) ) {
		if(n+m == 0) break; 
		ss.clear();
		int tmp;
		for(int i =1; i<=n; i++) {
			scanf("%d",&tmp);
			ss.insert(tmp);
		}
		int cnt = 0;
		set<int, greater<int> > :: iterator it; 
		for(it = ss.begin(); it!=ss.end(); it++) {
			cnt++;
			printf("%d%c",*it,cnt==m?'\n':' ');
			if(cnt == m) break;
		}
	}
	return 0 ;
}