堆排——数据结构实验之排序四:寻找大富翁
数据结构实验之排序四:寻找大富翁Time Limit:?200 ms Memory Limit:?512 KiB Submit Statistic Problem Description 2015胡润全球财富榜调查显示,个人资产在1000万以上的高净值人群达到200万人,假设给出N个人的个人资产值,请你快速找出排前M位的大富翁。 Input 首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10),其中N为总人数,M为需要找出的大富翁数目,接下来给出N个人的个人资产,以万元为单位,个人资产数字为正整数,数字间以空格分隔。 Output 一行数据,按降序输出资产排前M位的大富翁的个人资产值,数字间以空格分隔,行末不得有多余空格。 Sample Input 6 3 12 6 56 23 188 60 Sample Output 188 60 56 Hint 请用堆排序完成。 该题是时间限制的很紧,所以使用堆排序,理清思路,慢慢编写。 #include using namespace std; int a[1000001]; void HeapAdjust(int a[],int i,int m) { int t,q; t = i; while(2 * i <= m) { if(a[i] < a[2 * i]) { t = 2 * i; } if(a[t] < a[2 * i + 1] && 2 * i + 1 <= m) { t = 2 * i + 1; } if(t == i) { break; } if(t != i) { q = a[t]; a[t] = a[i]; a[i] = q; i = t; } } } void Heapsort(int a[],int m) { int t; while(m >= 1) { t = a[1]; a[1] = a[m]; a[m] = t; m--; HeapAdjust(a,1,m); } } int main(void) { int n,m,i,x; scanf("%d %d",&n,&m); for(i = 1; i <= m; i++) { scanf("%d",&a[i]); } for(i = m / 2; i <= m; i++) { HeapAdjust(a,m); } Heapsort(a,m); for(i = m + 1; i <= n; i++) { scanf("%d",&x); if(x > a[1]) { a[1] = x; HeapAdjust(a,m); Heapsort(a,m); } } for(i = m; i >= 1; i--) { printf("%d%c",a[i],i == 1 ?'n':' '); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |