题目

阵前第一功 Time Limit: 1000 MS Memory Limit: 65536 KB Total Submissions: 207 Accepted: 87

Description

A国每个国民都有一定战斗力，每年国家都要对人民的战斗力进行一次排序统计，他们的排序规矩是相同战斗力的排名一样，而且只占一个排序名额。比如，有5个人：100,100,90,90,70. 两个100的并列第一，称为第一战斗力，两个90的并列第二，称为第二战斗力，依次类推。。。现在你想查询第K战斗力是多少

Input

先输入一个整数T，表示T（T<50）组数据。 每组第一行一个正整数N（1000>N>0），表示表示有N个人。接下里一行N个正整数ai(2^30>=ai>=0)，表示每个人的战斗力。 接下输入一个正整数K（N>=K>0）。（保证输入都合法）

Output

输出第K战斗力,输出占一行

Sample Input

2 5 100 90 90 100 70 2 10 1 2 3 3 3 400 3 4 3 1 4

Sample Output

90 2

思路

本题思路不难，获取输入后排个序，然后设置一个计数器，遍历输入，遇到与上一个不同的元素计数器+1，直到计数器与K相等，然后输出当前指向的元素。 然而实现起来有个很麻烦的地方:以什么为标准遍历输入数组？直接用迭代器遍历的话计数器在什么时候改变？用计数器遍历的话迭代器在什么时候改变？ 即究竟是

for (int count = 1; count < K; count++)

还是

for (vector<int>::iterator iter = ivec.begin(); iter < ivec.end(); iter++)

结论是两个都不好。在这里应该改变以往写for的思路，把里面的条件分开思考，而不是生硬的糅合在一起，该是什么就是什么，不为了单纯的统一for中的语句而强行使用某个变量来设置循环。

实现代码

#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main (void){ int TestTimes = 0, Times = 0; cin >> TestTimes; while (Times++ < TestTimes){ vector<int> ivec; int K = 0, count = 0, N = 0; cin >> N; for (int count = 0; count < N; count++){ int INPUT = 0; cin >> INPUT; ivec.push_back(INPUT); } cin >> K; sort(ivec.begin(), ivec.end(), greater<int>()); vector<int>::iterator iter = ivec.begin()+1; for (int count = 1; count < K; iter++) if (*iter != *(iter-1)) count++; cout << *(iter-1) << endl; } return 0; }

这里有一些细节需要注意： 1. 迭代器的定义在for外面，因此不用担心循环结束后迭代器消失，可以继续使用。 2. 迭代器初始化的值是ivec.begin()+1，这是因为循环中计数器增加的条件是if (iter != (iter-1))，如果iter从ivec.begin()开始，则在第一次循环中迭代器会超界（第1、2个元素不同会造成结果的变化） 3. 计数器count初始化的值是1，因为正常人不会从0开始计数= =（除了走火入魔的程序猿）。 4. 输出的是*(iter-1)，因为在for最后结束后，其条件改变语句（iter++）会再执行一次，这时iter指向的结果不是我们想要的。

作死的尝试

前两天在书上看到了priority_queue，优先队列，十分感兴趣，这玩意和vector有点像，但是可以自动的把数据从大到小排列，想到这次的题目也要排个序，不禁恶向胆边生（雾），作死的来试一试这个东西。 代码：

#include <iostream> #include <queue> using namespace std; int main (void){ int TestTimes = 0, Times = 0; cin >> TestTimes; while (Times++ < TestTimes){ priority_queue<int> ipq; int K = 0, count = 0, N = 0; cin >> N; for (int count = 0; count < N; count++){ int INPUT = 0; cin >> INPUT; ipq.push(INPUT); } cin >> K; int flag = ipq.top(); for (int count = 1; count < K; ipq.pop()) if (flag != ipq.top()) {count++; flag = ipq.top();} cout << flag << endl; } return 0; }

相对于vector来说，proprity_queue能进行的操作及其有限，因为它在本质上还是个队列，而不是数组（或者向量），具体能进行什么操作请自行查找。 我在使用的遇到的问题有两个： 1. 这玩意没有迭代器！！！没有迭代器！！！没有迭代器！！！想读取只能pop()或者top()，这意味着你不能直接访问中间的元素。我简直X了狗。。。。 2. 在循环的时候，条件是ipq.pop()，这意味着你在循环过后你需要的那个元素被pop掉了！！！被pop掉了！！！被pop掉了！！！(╯‵□′)╯︵┻━┻ 刚开始的时候我的输出是cout << ipq.top() << endl;结果输出死活不对，和原代码一对比才发现这个问题，所幸在循环的过程中队列中第一个元素被flag保存下来了，这才能够输出正确答案。

从结果上来说，使用vector和priority_queue并没有什么区别，但是代码长度由原来的 736 B缩短到了 612 B，这是一个伟大的成就！！！（啪啪啪啪啪啪、、(o゜▽゜)o☆[BINGO!]）然而并没有什么卵用。。。