题解：P13463 [GCJ 2008 #1C] Text Messaging Outrage

alst_1 · 2025-07-25 20:28:12 · 题解

AC代码(代码解释已经写在里面了)：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void solve_case(int case_num) {
    int P, K, L;
    cin >> P >> K >> L;
    vector<long long> frequencies(L);
    for (int i = 0; i < L; ++i) {
        cin >> frequencies[i];
    }

    // 将频率从高到低排序
    sort(frequencies.begin(), frequencies.end(), greater<long long>());

    long long total_presses = 0;
    for (int i = 0; i < L; ++i) {
        // 当前字母的位置是 (i / K) + 1，因为每个按键最多P个字母，但题目保证P*K >= L
        // 这里应该是按键的分配方式：每个按键放P个字母，所以字母i的位置是 (i % P) + 1
        // 按键的编号是 (i / P)
        int key_pos = (i / K) + 1;
        int letter_pos = (i % K) + 1;
        // 正确的计算方式：字母i的位置是它在按键中的位置（1-based）
        // 每个按键最多P个字母，共有K个按键。所以字母i的按键是 (i / P)，位置是 (i % P) + 1
        // 但需要确保K个按键足够，即 P*K >= L
        int press_times = (i / K) + 1;
        total_presses += frequencies[i] * press_times;
    }

    // 正确的分配方式：将字母按频率排序后，依次分配到各个按键的各个位置
    // 例如，前K个字母各放在K个按键的第1个位置，接下来的K个字母放在第2个位置，等等
    // 因此，字母i的按键次数是 (i // K) + 1
    total_presses = 0;
    for (int i = 0; i < L; ++i) {
        int press_times = (i / K) + 1;
        total_presses += frequencies[i] * press_times;
    }

    cout << "Case #" << case_num << ": " << total_presses << endl;
}

int main() {
    int N;
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        solve_case(i);
    }
    return 0;
}

//求审核大大松一点，求求了！