本文主要是介绍zoj - 2511 - Design T-Shirt,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:N个人为M个elements投票,计算各个element的票数和,选出最高的K个,逆序输出下标。
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1511
——>>题目本来不难,用优先队列来获取票数最高的K个下标即可,不料,一个疏忽,重载 < 时少了一个条件——在票数相同时选择下标较小的那个……WA了2次!!!
#include <iostream>
#include <queue>
#include <algorithm>using namespace std;const int maxn = 10000 + 10; //最大element数struct node //结点数据类型
{int indice; //element的下标,最小为1double sum; //该element得到的总分数node():sum(0){} //初始化为0
};bool operator < (node e1, node e2) //定义优先队列的排序方式,注意别漏了第二个条件!!!
{return ((e1.sum < e2.sum) || (e1.sum == e2.sum && e1.indice > e2.indice));
}int main()
{int N, M, K, i, j;double temp;node *element; //不知道最大有几个element,开个动态的数组来存while(cin>>N>>M>>K){element = new node[M+1]; //申请空间for(i = 1; i <= N; i++)for(j = 1; j <= M; j++){cin>>temp;element[j].indice = j; //保存各个element的下标element[j].sum += temp; //累加各个element的分数和}priority_queue<node> qu; //程序的核心,优先队列for(i = 1; i <= M; i++) //各个element入列qu.push(element[i]);int id[maxn]; //用来存选出来的K个elements的下标for(i = 1; i <= K; i++){id[i-1] = qu.top().indice; //取选出来的K个elements的下标qu.pop();}sort(id, id+K); //排序for(i = K-1; i > 0; i--) //逆序输出cout<<id[i]<<" ";cout<<id[0]<<endl;}return 0;
}
这篇关于zoj - 2511 - Design T-Shirt的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!