首页 > ACM题库 > HDU-杭电 > HDU 3785-寻找大富翁-数据结构-[解题报告]HOJ
2015
04-13

HDU 3785-寻找大富翁-数据结构-[解题报告]HOJ

寻找大富翁

问题描述 :

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

输入:

输入包含多组测试用例.
每个用例首先包含2个整数n(0<n<=100000)和m(0<m<=10),其中: n为镇上的人数,m为需要找出的大富翁数, 接下来一行输入镇上n个人的财富值.
n和m同时为0时表示输入结束.

输出:

输入包含多组测试用例.
每个用例首先包含2个整数n(0<n<=100000)和m(0<m<=10),其中: n为镇上的人数,m为需要找出的大富翁数, 接下来一行输入镇上n个人的财富值.
n和m同时为0时表示输入结束.

样例输入:

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

样例输出:

5
5 4 3

STL最大堆算法

http://blog.csdn.net/fdl19881/article/details/6685744

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
#include<functional>
int n,m;
std::vector<int> men;
 
int in;
int main()
{
	while (std::cin>>n>>m&&(m!=0||n!=0)){
		
		if(m>=n){
			for( int i = 0 ; i < n; ++i ){ 
				std::cin>>in;
				men.push_back(in);
			}  
			std::sort(men.begin(),men.end(),std::greater<int>());
		}else{
			for( int i = 0 ; i < m; ++i ){ 
				std::cin>>in;
				men.push_back(in);
			}  

			std::make_heap( men.begin() , men.end() , std::greater<int>() ); 
			int i=m;
			while(i!=n){  
				scanf("%d",&in);

				if ( men.front() < in ){  
					std::pop_heap( men.begin() , men.end() , std::greater<int>() );  
					men.pop_back();  
					men.push_back(in);  
					std::push_heap( men.begin() , men.end() , std::greater<int>() );  
				}  
				i++;
			}  
			std::sort_heap( men.begin() , men.end() , std::greater<int>() );  
		}
		
		std::cout<<men[0];
		for(int i=1;i!=m;i++){
			std::cout<<" "<<men[i];
		}
		std::cout<<std::endl;
		men.clear();
	}
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/emiyasstar__/article/details/9132577


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?