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

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

// 模块结构体，用于优先队列
struct Module {
    long long current_t;
    long long limit_b;
    
    // 计算当前优化一次能减少的耗时
    long long get_reduction() const {
        long long next_t = max(limit_b, (current_t + 1) / 2);
        return current_t - next_t;
    }
    
    // 大顶堆比较规则
    bool operator<(const Module& other) const {
        return get_reduction() < other.get_reduction();
    }
};

int main() {
    int n;
    long long k;
    cin >> n >> k;
    
    vector<long long> a(n), b(n);
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total_sum += a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    
    priority_queue<Module> pq;
    for (int i = 0; i < n; ++i) {
        pq.push({a[i], b[i]});
    }
    
    while (k > 0 && !pq.empty()) {
        Module top = pq.top();
        pq.pop();
        
        long long reduction = top.get_reduction();
        if (reduction <= 0) break; // 无法再进一步优化
        
        total_sum -= reduction;
        top.current_t = max(top.limit_b, (top.current_t + 1) / 2);
        pq.push(top);
        k--;
    }
    
    cout << total_sum << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Module implements Comparable<Module> {
        long currentT;
        long limitB;
        
        Module(long currentT, long limitB) {
            this.currentT = currentT;
            this.limitB = limitB;
        }
        
        long getReduction() {
            long nextT = Math.max(limitB, (currentT + 1) / 2);
            return currentT - nextT;
        }
        
        @Override
        public int compareTo(Module other) {
            return Long.compare(other.getReduction(), this.getReduction());
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        
        long[] a = new long[n];
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            totalSum += a[i];
        }
        
        long[] b = new long[n];
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextLong();
        }
        
        PriorityQueue<Module> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.add(new Module(a[i], b[i]));
        }
        
        while (k > 0 && !pq.isEmpty()) {
            Module top = pq.poll();
            long reduction = top.getReduction();
            if (reduction <= 0) break;
            
            totalSum -= reduction;
            top.currentT = Math.max(top.limitB, (top.currentT + 1) / 2);
            pq.add(top);
            k--;
        }
        
        System.out.println(totalSum);
    }
}

import heapq

def solve():
    # 读取输入
    line1 = input().split()
    n, k = int(line1[0]), int(line1[1])
    
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    
    total_sum = sum(a_list)
    
    # Python 的 heapq 是小顶堆，存负值实现大顶堆
    # 堆元素：(-减少的耗时, 当前耗时, 下限)
    pq = []
    for i in range(n):
        reduction = a_list[i] - max(b_list[i], (a_list[i] + 1) // 2)
        if reduction > 0:
            heapq.heappush(pq, (-reduction, a_list[i], b_list[i]))
            
    while k > 0 and pq:
        neg_red, cur_t, limit_b = heapq.heappop(pq)
        reduction = -neg_red
        
        total_sum -= reduction
        k -= 1
        
        # 更新当前耗时
        new_t = max(limit_b, (cur_t + 1) // 2)
        # 计算下一次优化的减少量
        new_reduction = new_t - max(limit_b, (new_t + 1) // 2)
        if new_reduction > 0:
            heapq.heappush(pq, (-new_reduction, new_t, limit_b))
            
    print(total_sum)

solve()