做catia数据的网站,直播网站开发费,建设局全称,四川省住房和城乡建设局网站首页题干#xff1a; 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁.
Input输入包含多组测试用例. 每个用例首先包含2个整数n#xff08;0n100000#xff09;和m(0m10)#xff0c;其中: n为镇上的人数#xff0c;m为需要找出的大富翁数, 接下来一行输入…题干 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁.
Input输入包含多组测试用例. 每个用例首先包含2个整数n0n100000和m(0m10)其中: 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
#includeiostream
#includecstring
#includecstdio
#includealgorithm
using namespace std;int a[1000005];
int main()
{int n,m;while(~scanf(%d%d,n,m)) {if(n0m0) break;memset(a,0,sizeof(a));for(int i 1; in; i) {scanf(%d,a[i]);}sort(a1,an1, greaterint() );if(nm) {for(int i 1; in; i) {printf(%d%c,a[i],in?\n: ); }continue;}if(nm) {for(int i 1; i m; i) {printf(%d%c,a[i],im?\n: ); }}}return 0 ;
}
事实证明不加if(nm)的情况 也能ac看来是样例中没出这样的样例不然依照题干应该是有这一种情况发生啊。 优先队列ac
#includecstdio
#includeiostream
#includequeue
using namespace std;
priority_queueint,vectorint,lessint q;//等价于priority_queueint q; 从大到小排序
int main()
{int n,t,a;while(scanf(%d %d,n,t)(n!0||t!0)){for(int i0;in;i){scanf(%d,a);q.push(a);}for(int i0;it-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 i0;in;i){scanf(%d,a);q.push(a);}for(int i0;it-1;i){printf(%d ,q.top());q.pop();}printf(%d,q.top());//最有一个数字没有空格。printf(\n);//每次别忘清空队列while(!q.empty()) q.pop();}return 0;
}优先队列ac2优化了nm的情况源自网络
/*
当输入小于m个的时候一直输入当输入大于m个数之后 这m个数会按照从小到大的顺序排序
再往里面输入的时候要进行判断如果那个数比对顶元素大的话这个数进队对顶元素出对
进队后就又变成从小到大排序了输入完毕之后将数据按从大到小输出因为对顶元素是最小值
所以应该将元素 都重新赋值到数组中然后从后往前输出就这个转换方法必须想到
*/
#include stdio.h
#include queue
#include algorithm
using namespace std;
priority_queueint,vectorint,greaterint 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(i0; in; i) { //将财产值放到队列中scanf(%d,a);if(q.size()m)q.push(a);else if(aq.top()) {q.push(a);q.pop();}}if(nm) { //当总人数比富翁人数多的话执行下面语句for(i0; im; i) {b[i]q.top();q.pop();}for(im-1; i0; i--)printf(%d ,b[i]);printf(%d\n,b[0]);} else { //总人数没有富翁人数多的话执行这个下面的语句for(i0; in; i) {b[i]q.top();q.pop();}for(in-1; i0; i--)printf(%d ,b[i]);printf(%d\n,b[0]);}}return 0;
} 今天又用set实现了一下第一发错了后来发现需要multiset
AC代码
#includebits/stdc.husing namespace std;
multisetint,greaterint ss;
int main()
{int n,m;while(~scanf(%d%d,n,m) ) {if(nm 0) break; ss.clear();int tmp;for(int i 1; in; i) {scanf(%d,tmp);ss.insert(tmp);}int cnt 0;setint, greaterint :: iterator it; for(it ss.begin(); it!ss.end(); it) {cnt;printf(%d%c,*it,cntm?\n: );if(cnt m) break;}}return 0 ;
}
