C26F:Phigros Rating

http://poj.openjudge.cn/practice/C26F/

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, B;
    cin >> N >> B;

    vector<double> scores;
    scores.reserve(N);

    for (int i = 0; i < N; i++) {
        int d, acc;
        cin >> d >> acc;

        double contribution = 0.0;

        if (acc == 100) {
            contribution = d * 1.0;
        } else if (acc >= 95) {
            contribution = d * (0.5 + acc / 200.0);
        } else if (acc >= 70) {
            contribution = d * (acc / 150.0 - 1.0 / 6.0);
        } else {
            contribution = 0.0;
        }

        scores.push_back(contribution);
    }

    sort(scores.begin(), scores.end(), greater<double>());

    int k = min(N, B);
    double sum = 0.0;

    for (int i = 0; i < k; i++) {
        sum += scores[i];
    }

    cout << fixed << setprecision(6) << sum / k << '\n';

    return 0;
}

这道题目是一个典型的贪心算法应用题。题目要求根据给定的难度系数 $d$ 和正确率 $a c c$ 计算每项得分，最后选取表现最好的 $B$ 项计算平均分。

Python 代码实现

python

import sys

def solve():
    # 使用 sys.stdin.read().split() 一次性读取所有数据，处理速度最快
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N 是总条目数，B 是计算平均分时考虑的最大条目数
    n = int(input_data[0])
    b = int(input_data[1])
    
    scores = []
    current_idx = 2
    
    for _ in range(n):
        d = int(input_data[current_idx])
        acc = int(input_data[current_idx + 1])
        current_idx += 2
        
        # 根据题目给出的公式计算单项贡献分
        contribution = 0.0
        
        if acc == 100:
            contribution = float(d)
        elif acc >= 95:
            # 公式 1: d * (0.5 + acc / 200)
            contribution = d * (0.5 + acc / 200.0)
        elif acc >= 70:
            # 公式 2: d * (acc / 150 - 1/6)
            contribution = d * (acc / 150.0 - 1.0 / 6.0)
        else:
            # 低于 70 分不计分
            contribution = 0.0
            
        scores.append(contribution)
    
    # 贪心策略：将计算出的贡献分从大到小排序
    scores.sort(reverse=True)
    
    # 取前 B 个得分（如果总数不足 B，则取全部 N 个）
    k = min(n, b)
    
    if k == 0:
        print(f"{0.0:.6f}")
        return
    
    # 计算前 k 项的和
    top_sum = sum(scores[:k])
    
    # 计算平均分并保留 6 位小数
    result = top_sum / k
    print(f"{result:.6f}")

if __name__ == "__main__":
    solve()

代码解读

1. 分段得分逻辑

题目根据正确率 $a c c$ 的不同，设定了不同的权重系数：

满分 ( $100$ )：全额计分。
优秀 ( $95 \leq a c c < 100$ )：系数在 $0.975$ 到 $1.0$ 之间波动。
及格 ( $70 \leq a c c < 95$ )：系数在 $0.3$ 到 $0.466$ 之间波动。
不及格 ( $< 70$ )：不计分。

在 Python 中，直接使用浮点数除法（/）即可精确还原 C++ 中的 double 运算。

2. 贪心策略

题目要求最终的平均分最高。由于分母 $k$ 是固定的（即 $m i n (N, B)$ ），要使平均分最大，分子（总得分）就必须最大。因此，我们将所有计算出的得分进行从大到小排序，并截取前 $B$ 个。

3. 性能优化

输入：sys.stdin.read().split() 将整个输入流读入并切分成列表，比循环调用 input() 处理几万行数据时速度快得多。
排序：Python 内置的 sort(reverse=True) 使用的是 Timsort 算法，处理这种规模的排序非常高效。
输出：使用 f-string 的 :.6f 格式化，可以精确控制输出 6 位小数，满足题目精度要求。

C26F:Phigros Rating ​

Python 代码实现 ​

代码解读 ​

1. 分段得分逻辑 ​