Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

Archer's blog

博客

分类

标签

归档

友链

Codeforce Next Round

算法竞赛Codeforce

算法竞赛

Codeforce

800

更新于：Apr 2, 2025

题目描述

image-20250325224420596

思路

先统计前 k 个分数中大于 0 的数量。因为分数是递减排列的，只需继续统计从第 k 个位置开始，所有与第 k 个分数相等的连续分数个数。最后的总合就是结果。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n_k = input().split()
n = int(n_k[0])
k = int(n_k[1])

n_list = list(map(int, input().split()))

comp = n_list[k-1]

n1_list = n_list[:k]  

for i in range(k,n):
    if n_list[i] == comp:
        n1_list.append(n_list[i])
    else:
        break

count = sum(1 for x in n1_list if x > 0)
# print(n1_list)
print(count)

优化：

1
2
3
4
n, k = map(int, input().split())
scores = list(map(int, input().split()))
threshold = scores[k - 1]
print(sum(s >= threshold and s > 0 for s in scores))

用numpy的：

1
2
3
4
5
6
7
import numpy as np

n, k = map(int, input().split())
scores = np.array(list(map(int, input().split())))
threshold = scores[k - 1]
result = np.sum((scores >= threshold) & (scores > 0))
print(result)

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    int scores[100];  // 假设最大不超过 100 个分数
    for (int i = 0; i < n; i++) {
        scanf("%d", &scores[i]);
    }

    int threshold = scores[k - 1];  // 第 k 个选手的分数（索引从 0 开始）
    int count = 0;

    // 前 k 个中统计 >0 且 >= threshold 的分数
    for (int i = 0; i < k; i++) {
        if (scores[i] >= threshold && scores[i] > 0) {
            count++;
        }
    }

    // 从第 k 个开始，统计连续等于 threshold 的（也必须 >0）
    for (int i = k; i < n; i++) {
        if (scores[i] == threshold && scores[i] > 0) {
            count++;
        } else {
            break;
        }
    }

    printf("%d\n", count);

    return 0;
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> scores(n);
    for (int i = 0; i < n; ++i) {
        cin >> scores[i];
    }

    int threshold = scores[k - 1];
    int count = 0;

    for (int i = 0; i < n; ++i) {
        if (scores[i] >= threshold && scores[i] > 0) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

用ranges：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <ranges>
using namespace std;
namespace ranges = std::ranges;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> scores(n);
    for (int& score : scores) {
        cin >> score;
    }

    int threshold = scores[k - 1];

    auto advancers = scores 
                   | ranges::views::filter([threshold](int x) {
                         return x >= threshold && x > 0;
                     });

    cout << ranges::distance(advancers) << endl;
    return 0;
}

Remark

1. 如果只是

1
n,k = input().split()

的话只会将n,k赋值成2个string，而不是int，所以需要这一步将它们转成2个int：

1
2
3
n_k = input().split()
n = int(n_k[0])
k = int(n_k[1])

list那里的处理也是同理。

2. 如果直接写

1
2
3
4
5
6
7
8
n_list = list(map(int, input().split()))
comp = n_list[k-1]

for i in range(k,n):
    if n_list[i] == comp:
        n_list.append(n_list[i])
    else:
        break

的话，会导致遍历一个列表的同时又在修改它，会导致结果不可控。

但就算是改成了

1
2
3
4
5
6
7
8
9
10
n_list = list(map(int, input().split()))

comp = n_list[k-1]

n1_list = n_list
for i in range(k,n):
    if n1_list[i] == comp:
        n_list.append(n1_list[i])
    else:
        break

也不对，因为在python里n1_list 并不是 n_list 的复制品，而只是同一个列表的两个名字。这样只是让 n1_list 和 n_list 指向同一个列表对象，修改任何一个，都会影响另一个。所以会出现跟之前一模一样的结果。

创建独立的副本需要：

1
2
3
4
5
6
n1_list = n_list[:]
# 或
n1_list = list(n_list)
# 或
import copy
n1_list = copy.copy(n_list)

（注意：python里的list[a:b]是前闭后开，所以这个不包含list[b]）

3. 假如这道题的input是乱序的，那么需要先将input排序了再进行后续操作。

python的话非常简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
input = [3, 1, 4, 1, 5, 9]

#升序：

input.sort()              # 原地排序，修改 input 本身
# 或者
input = sorted(input)       # 返回新排序后的列表


#降序：
input.sort(reverse=True)
# 或者
input = sorted(input, reverse=True)

c就很麻烦了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);  // 升序
    // return (*(int *)b - *(int *)a);  // 降序
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, n, sizeof(int), cmp);  // 排序调用

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

因为 qsort()（通用的排序函数）是泛型函数，它不能直接比较 int 或 float，我们必须手动告诉它“怎么比较两个值”。

相比之下c++就会方便很多，因为有内置的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#include <functional>			// 降序会需要

using namespace std;

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);  // 默认升序排序
    // sort(arr, arr + n, greater<int>());	降序

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

也可以直接用cpp的 vector<int>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};

    sort(v.begin(), v.end());  // 升序
    // sort(v.begin(), v.end(), greater<int>());  // 降序

    for (int x : v) {
        cout << x << " ";
    }

    return 0;
}

发布于：Mar 25, 2025