AOJ 843.晋级下一轮

195


题目


点击显/隐题目

比赛规定,N个人的比赛,分数为正数且分数大于等于第K名分数的人可以晋级下一轮。

现在给N个人的分数,问有多少个人可以晋级。注意,分数越高,排名越靠前。





第一行,一个整数t,表示测试数据组数(1<=t<=100)
每组测试数据:
第一行两个整数,n和k,(1<=k<=n<=100)
第二行n个整数,表示每个人的分数,已经从高到低排列,(0<=每个人的分数<=100)





每组测试数据,一个整数,表示有多少个人可以晋级下一轮。





2
8 5
10 9 8 7 7 7 5 5
4 2
0 0 0 0





6
0





题解



找出所有比要求排名数分数高且分数不为 0 的人数

简单点写就是先找到排名为 k 的人,获取他的分数,大于 0 就找比他小的,等于 0 就找比他大的第一个不是 0
lower_bound()upper_bound() 虽然非常快,但是反而出错几率会变大

代码


点击显/隐代码
`cpp 晋级下一轮 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include
//*/
#include
#include
#include
#include
using namespace std;

const int maxn = 105;
int a[maxn];

typedef int LL;

int lowerbound(LL arr,int size, LL key) {
int half;
int mid;
int first = 0;
while (size > 0) {
half = size >> 1;
mid = first + half;
if (arr[mid] > key) {
first = mid + 1;
size = size - half - 1;
} else {
size = half;
}
}
return first;
}
int upperbound(LL arr,int size, LL key) {
int half;
int mid;
int first = 0;
while (size > 0) {
half = size >> 1;
mid = first + half;
if (arr[mid] >= key) {
first = mid + 1;
size = size - half - 1;
} else {
size = half;
}
}
return first;
}

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.syncwithstdio(false);

int T;
cin >> T;
while(T--){
int n,k;
cin >> n >> k;
for(int i=0;icin >> a[i];

k = a[k-1];
if(!k)
cout << lower_bound(a,n,k) << endl;
else
cout << upper_bound(a,n,k) << endl;
}

#ifdef debug
printf("Time:%.3fs.n", double(clock() - START) / CLOCKSPERSEC);
#endif
return 0;
}

发布评论
  • 点击查看/关闭被识别为广告的评论