#P2827. 第2题-小苯的数组
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 61
            Accepted: 14
            Difficulty: 5
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年4月12日-阿里淘天(算法岗)
                              
                      
          
 
- 
                        算法标签>贪心算法          
 
第2题-小苯的数组
题解
题面描述
给定一个长度为n的序列a,总共进行m次操作,每次操作按如下规则进行:
- 在序列a中,找到最小元素中最靠前(下标最小)的那个,其余所有数都减去k。
 
要求输出所有操作结束后序列a中每个数的最终值。
思路
直接模拟每一次操作时间复杂度较高,考虑到n和m的上界均为2×105。观察操作规则不难发现,每一次操作对所有数都会扣除k,而仅有一个数会“补回”这一k。
于是,我们可以把最终结果写成:
aifinal=ai−m×k+ti×k其中ti表示第i个数在m次操作中没有被扣k的次数(即被“保留”的次数)。显然有
i=1∑nti=m操作规则要求:每一步选出的那个数一定是当前所有数中(扣除相同全局减去的k后)最小的。
设当前该数已经“保留”了ti次,则它的当前实际值为
ai−current=ai−(操作步数−ti)×k注意到对于所有数,在某一步操作时,公共部分−(操作步数)×k相同,因此只需比较
ai+ti×k即在每一步,选出使得ai+ti×k最小的数(若存在相等则选下标更小的),令其ti加1。
这样最终的答案就可以表示为
aifinal=ai−(m−ti)×k我们可以利用优先队列来维护每个数的当前“键值”ai+ti×k,初始时所有ti=0;每次从优先队列中取出最小值,对应数的ti加1后,将其新的键值更新为ai+(ti+1)×k后重新放入队列。经过m次操作后,每个数被“保留”了ti次,最终答案即为上式所示。
代码分析
- 数据结构:
使用优先队列(小根堆),存储每个元素的结构为{key,idx,t},其中key=ai+ti×k。 - 比较规则:
按照key排序,若key相同则按下标idx从小到大优先。 - 更新过程:
循环m次,每次取队首元素,将该位置的ti加一,并计算新的key=ai+(ti+1)×k后再插回队列。 - 最后输出:
遍历所有下标,最终值为aifinal=ai−(m−ti)×k 
C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
// 定义节点结构体:存储当前键值、下标和保存次数
struct Node {
    long long key; // key = a[i] + t[i] * k
    int idx;      // 数组下标
    int t;        // 保留次数 t[i]
};
 
// 自定义比较函数:先比较 key,若相等则比较下标
struct cmp {
    bool operator()(const Node &a, const Node &b) const {
        if(a.key == b.key) return a.idx > b.idx;
        return a.key > b.key;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        int n, m, k;
        cin >> n >> m >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; i++){
            cin >> a[i];
        }
 
        // 初始时所有数 t[i] = 0, key = a[i]
        priority_queue<Node, vector<Node>, cmp> pq;
        vector<int> t(n, 0);
        for(int i = 0; i < n; i++){
            pq.push({a[i], i, 0});
        }
 
        // 进行 m 次操作,每次从 pq 取出最小 key 的元素,将其 t 值加一后更新 key 后再入队
        for(int op = 0; op < m; op++){
            Node cur = pq.top();
            pq.pop();
            cur.t++; // 该元素保留次数加一
            t[cur.idx] = cur.t;
            cur.key = a[cur.idx] + (long long)cur.t * k; // 更新 key
            pq.push(cur);
        }
 
        // 输出每个元素最后的结果: a[i] - (m - t[i]) * k
        for(int i = 0; i < n; i++){
            long long res = a[i] - (long long)(m - t[i]) * k;
            cout << res << " ";
        }
        cout << "\n";
    }
    return 0;
}
Python
import sys
import heapq
input = sys.stdin.readline
# 读取测试数据组数
T = int(input())
for _ in range(T):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    # 初始化每个元素的保留次数 t[i] 为 0
    t = [0] * n
    # 构造优先队列,存放元素 (key, index, t)
    # key = a[i] + t[i] * k, 初始时 t[i] = 0, 所以 key = a[i]
    pq = [(a[i], i, 0) for i in range(n)]
    heapq.heapify(pq)
    
    # 进行 m 次操作,每次选出队列中 key 最小的元素
    for _ in range(m):
        key, idx, cnt = heapq.heappop(pq)
        cnt += 1           # 增加该位置的保留次数
        t[idx] = cnt       # 更新记录
        new_key = a[idx] + cnt * k  # 更新 key 值
        heapq.heappush(pq, (new_key, idx, cnt))
    
    # 输出最终结果,最终值为: a[i] - (m - t[i]) * k
    res = [str(a[i] - (m - t[i]) * k) for i in range(n)]
    sys.stdout.write(" ".join(res) + "\n")
Java
import java.io.*;
import java.util.*;
 
public class Main {
    // 节点类,存储 key, idx, t 值
    static class Node {
        long key; // key = a[i] + t[i] * k
        int idx;
        int t;
 
        public Node(long key, int idx, int t) {
            this.key = key;
            this.idx = idx;
            this.t = t;
        }
    }
 
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
 
        while (T-- > 0) {
            String[] params = br.readLine().split(" ");
            int n = Integer.parseInt(params[0]);
            int m = Integer.parseInt(params[1]);
            int k = Integer.parseInt(params[2]);
 
            long[] a = new long[n];
            String[] aStr = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(aStr[i]);
            }
 
            // 数组 t 存储每个位置的保留次数,初始为 0
            int[] tArr = new int[n];
 
            // 自定义小根堆,比较规则:先比较 key,再比较下标
            PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
                public int compare(Node o1, Node o2) {
                    if (o1.key == o2.key) return o1.idx - o2.idx;
                    return Long.compare(o1.key, o2.key);
                }
            });
 
            // 将所有元素插入优先队列,初始 key = a[i]
            for (int i = 0; i < n; i++) {
                pq.offer(new Node(a[i], i, 0));
            }
 
            // 进行 m 次操作,每一次弹出 key 最小的节点,更新其 t 后重新插入
            for (int op = 0; op < m; op++) {
                Node cur = pq.poll();
                cur.t++; // 增加保留次数
                tArr[cur.idx] = cur.t;
                cur.key = a[cur.idx] + (long)cur.t * k; // 更新 key
                pq.offer(cur);
            }
 
            // 根据公式输出最终结果: a[i] - (m - t[i]) * k
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                long res = a[i] - (long)(m - tArr[i]) * k;
                sb.append(res).append(" ");
            }
            out.println(sb.toString().trim());
        }
        out.flush();
        out.close();
    }
}
        题目内容
给定一个长度为n的序列a,小苯希望你在a上进行m次操作,每次操作描述为:
- 除了a 中的最靠前的最小值以外的其余所有数,都会减小k。(注意,最小值有多个时选择最靠前,即下标最小的那个。)
 
现在小苯想问问你,在m 次操作后,序列a的所有元素值分别是多少,请你求一求吧。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≦T≦100)代数据组数,每组测试数据描述如下:
第一行三个正整数n,m,k(1≦n,m,k≦2×105),分别表示序列a的长度,操作进行的次数,以及每次操作减少的值。
第二行n 个正整数ai(1≦ai≦109),表示序列a。
除此之外,保证单个测试文件的n之和不超过2×105,m之和不超过2×105。
输出描述
对于每组测试数据:
在单独的一行输出n个整数,表示进行完所有操作后的序列a。
样例1
输入
2
6 2 3
13 11 15 20 12 11
4 1 1
1 1 1 1
输出
7 8 9 14 6 8
1 0 0 0
说明
对于第一组测试数据(每次操作选中的数字已经加粗):
初始时:a={13,11,15,20,12,11}。
操作1次后:a={10,11,12,17,9, 8}。
操作2次后: a={7,8,9,14,6,8}。