题解 | 魔导模块的效能迭代

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

if (!in.hasNextInt()) return;

int n = in.nextInt();

int m = in.nextInt();

int[] a = new int[n];

for (int i = 0; i < n; i++) {

a[i] = in.nextInt();

}

int[] b = new int[n];

for (int i = 0; i < n; i++) {

b[i] = in.nextInt();

}

// 定义大顶堆：存放 int[]{当前时间 t, 下限 b}

// 排序规则：按“本次优化能省下的时间”降序排列 (谁省得多，谁排前面)

PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {

int reduceX = x[0] - Math.max((x[0] + 1) / 2, x[1]);

int reduceY = y[0] - Math.max((y[0] + 1) / 2, y[1]);

return Integer.compare(reduceY, reduceX);

});

long sum = 0; // 用long防止各个数字加起来超出int范围

for (int i = 0; i < n; i++) {

sum += a[i]; // 先计算出没优化之前的总和

// 计算当前这个模块优化一次能省多少时间

int reduce = a[i] - Math.max((a[i] + 1) / 2, b[i]);

// 如果能省时间（>0），才放进队列

if (reduce > 0) {

pq.offer(new int[]{a[i], b[i]});

}

}

// 进行 m 天的优化

while (m > 0 && !pq.isEmpty()) {

// 挑出能省最多时间的模块

int[] curr = pq.poll();

int t = curr[0];

int limit = curr[1];

// 计算新耗时

int nextT = Math.max((t + 1) / 2, limit);

// 总时间减去省下来的时间

sum -= (t - nextT);

// 更新当前模块的时间

curr[0] = nextT;

// 如果这个模块还能继续优化，再扔回堆里，参与明天的竞争

int nextReduce = curr[0] - Math.max((curr[0] + 1) / 2, limit);

if (nextReduce > 0) {

pq.offer(curr);

}

m--;

}

System.out.println(sum);

}

}