题目

{% raw %}

点击显/隐题目

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

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

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

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

{% raw %}

{% endraw %}

6
0

{% raw %}

{% endraw %}

题解

找出所有比要求排名数分数高且分数不为 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 lower_bound(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 upper_bound(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.sync_with_stdio(false);

int T;
cin >> T;
while(T--){
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++)
        cin >> 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) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>

AOJ 843.晋级下一轮

题目

题解

代码