题目描述

贪心+排序：如果当前所有仍需要继续训练的士兵一次训练所需的金币总和小于 团购s的花费，就使用组团训；否则剩下的士兵全部单独训。

样例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class XunLianShiBing {
    static final int N = (int) (1e6 + 10);
    static long[] p = new long[N];// 花费
    static long[] c = new long[N];// 次数
    static long[] cnt = new long[N];// cnt[i] 为需要训练 i 次的士兵一次训练所需的金币之和
    static long Sum, now, ans;
    static long n, s; // s是团购的花费
    // Sum 为所有士兵单独训练所需的金币之和
    // now 为所有士兵一次训练所需的金币之和

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        String[] st0 = bf.readLine().trim().split("\\s+");
        n = Long.parseLong(st0[0]);
        s = Long.parseLong(st0[1]);

        long maxC = 0;
        for (int i = 1; i <= n; i++) {
            String[] st1 = bf.readLine().trim().split("\\s+");
            p[i] = Long.parseLong(st1[0]);
            c[i] = Long.parseLong(st1[1]);
            cnt[(int) c[i]] += p[i];
            now += p[i];
            Sum += p[i] * c[i];
            maxC = Math.max(maxC, c[i]);
        }

        for (int i = 1; i <= maxC; i++) {
            if (now < s)
                break;
            // 只有当前单独训的花费 > 团购的花费，才需要买团购
            ans += s;
            Sum -= now;
            now -= cnt[i];
        }

        pw.print(ans + Sum);
        pw.flush();
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla