蓝桥杯第17169题——兽之泪II

问题描述

在蓝桥王国，流传着一个古老的传说：在怪兽谷，有一笔由神圣骑士留下的宝藏。

小蓝是一位年轻而勇敢的冒险家，他决定去寻找宝藏。根据远古卷轴的提示，如果要找到宝藏，那么需要集齐 n 滴兽之泪，同时卷轴中也记载了，每击败一次怪物，就能够收集一滴兽之泪。

小蓝知道，这些怪物并非泛泛之辈，每一只都拥有强大的力量和狡猾的技巧。每一只怪物都有它独特的弱点和对策，小蓝必须谨慎选择战斗的策略和使用的能量。

在怪兽谷中，有 k 只怪兽。对于第 i 只怪兽，第一次击败他需要 xi​ 点能量，后续再击败他需要 yi​ 点能量。在挑战过程中，前 k−1 只怪兽可以随意挑战，但是第 k 只怪兽是怪兽之王，如果要挑战第 k 只怪兽，那么对于前 k−1 只怪兽都要击败至少一次。

小蓝想知道，如果要集齐 n 滴兽之泪，那么至少需要多少能量。

输入格式

第一行包含一个整数 T(T≤105)，代表测试组数。

每组数据包含如下部分：

第一行包含两个整数 k 和 n，表示怪物的数量和需要收集的兽之泪的数量。

2 ≤ k ≤ 10^5, 1 ≤ n ≤ 2 × 10^5。

接下来 k 行，每行包含两个整数 xi​ 和 yi​，表示第 i 只怪物第一次和后续击败所需的能量。

1 ≤ xi​, yi ​≤ 10^9。

保证 ∑k ≤ 10^5。

输出格式

对于每组数据，输出一个整数，表示小蓝至少需要多少点能量才能收集完成。

样例输入

1
3 4
2 2
4 2
1 1

样例输出

8

说明

注意，xi​,yi​ 并不保证谁大谁小。

一种可行的方案是：

1. 第一次选择 1 号怪物，消耗能量 2。
2. 第二次选择 2 号怪物，消耗能量 4。
3. 由于 1,2 都已经击败一次，所以可以选择 3 号，第三次选择 3 号怪物，消耗能量 1。
4. 第四次选择 3 号怪物，消耗能量 1。

另外一种方案是：

四次都选择 1 号怪兽，消耗的能量是 8。

解题思路

从数据量来看，解决该问题的时间复杂度不得达到O(N^2)，使用二分的情况下满足时间复杂度要求，并且题目给出限制条件k的总和低于10^5，因此对每组数据进行排序是符合O(nlogn)的复杂度的，所以可以明确，此题可以使用排序、二分。

此题可以从游戏玩家的角度去思考打怪兽策略，由于一个怪兽可以多次打，那么我们肯定会想要多次去刷同一个y值消耗低的怪兽，以此刷满掉落物。

那么假设我们要一直刷的怪兽，扫荡消耗yi能量，那么首次击败所消耗的能量低于yi的怪兽就应当优先击败一次，这样可以在刷yi怪兽之前做到能量消耗最少。

我们会考虑到遍历每组数据的所有x值，其比yi小的记录到cost里，但这种方式并不会超时，但是会有另外的问题：如果比yi小的x值数量已经满足n滴眼泪的要求，我们就需要提前返回最小的n个x值总和，如果是乱序的，每次从第一个x开始遍历，那么就无法找到不考虑y只考虑x的最小能量消耗情况（也就是只挑选部分怪兽打一次就够了的情况，无法计算出最小的x总和）

所以既然排序是允许的，那么我们干脆对每组数据的x先进行排序，并使用pre数组对x做前缀和的预计算，那么在上述提到的特例情况中，就可以直接返回pre[n]的值即可。

排序之后我们会想到一个这样的做法，但它是错的：我们遍历每一个怪兽，定义其序号为j，先刷完1到j每个怪兽1次，最后不够的再刷第j个怪兽。这个方法错误的原因在于，对于一个较大的x，可能会有一个相当小的y，直白的说，帅怪的顺序可能是x1，x2，x5，y5，y5，y5……在这个可能的策略中，我们跳过了x3和x4没有刷，这种情况是有可能发生的，所以这个方法是不可行的。

最终我们的做法是，对每组数据的每个y进行枚举，考虑最后无限刷的怪兽多次击败的能量消耗是y，期间使用二分法配合前缀和计算出刷它之前需要刷的其他怪兽能量消耗，就可以找到最小的答案。

import java.util.*;
import java.io.*;
 
public class Main{
    public static Pair[] pairs;
    public static long[] pre;
    public static int k, n;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            k = sc.nextInt();
            n = sc.nextInt();
            pairs = new Pair[k + 1];
            pre = new long[k + 1];
            for (int i = 1; i <= k; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                pairs[i] = new Pair(x, y);
            }
            // 对pairs数组的[1, k-1]进行排序，避免0下标的空指针问题
            // 第k个怪兽的x再小也不可以提前刷，必须维持在最后的位置
            Arrays.sort(pairs, 1, k, Comparator.comparing((Pair p) -> p.x));
            // 对于刷满k个怪兽的情况，后续不够的兽之泪可以刷y最小的那只怪兽
            long minY = Integer.MAX_VALUE;
            for (int i = 1; i <= k; i++) {
                pre[i] = pre[i - 1] + pairs[i].x;
                minY = Math.min(minY, pairs[i].y);
            }
            long ans = solveK(minY);
            for (int i = 1; i < k; i++) {
                ans = Math.min(ans, solve(i));
            }
            System.out.println(ans);
        }
    }
 
    public static long solveK(long minY) {
        long cost = pre[k];
        long tear = k;
        cost += Math.max(0, n - tear) * minY;
        return cost;
    }
 
    public static long solve(int yi) {
        Pair p = pairs[yi];
        // 此结构的二分下，最后的right是满足if表达式的最大下标
        int left = 1, right = k;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (pairs[mid].x < p.y) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 如果根本不需要刷那么多，就返回pre[n]提前结束
        if (right >= n) {
            return pre[n];
        }
        long cost = pre[right];
        long tear = right;
        // 如果yi对应的x没有杀过，就单独处理一下
        if (right < yi) {
            cost += p.x;
            tear++;
        }
        cost += Math.max(0, n - tear) * p.y;
        return cost;
    }
}
 
class Pair {
    int x, y;
 
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}