题解 | #集合操作#

集合操作(C) 题解

先将 数组排序，可以考虑二分。二分什么呢？答曰：二分答案。

当然，不是集合中的每个元素都要二分答案，我们只二分原来还没有开始操作时最大的元素()最后的大小。

我们假设 最后的大小排名第 ，不妨假设原 的元素最后的排名分布在 ，且尽可能小。

容易证明，当 最后的大小越小，需要操作的次数越多。

函数就很好写了

bool check (LL x) {
    LL temp = a[n] - x * p;//最后a[n]的大小
    LL sum = 0;//统计需要操作多少次
    for (int i = 1; i <= n; i++) {
        if (a[i] <= temp) continue;//排名在 [idx, n]
        sum += (a[i] - temp) / p;
    }
    return sum >= k;//当操作次数大于k时满足要求 
}

但还没完，我们还需要对它进行一定的调整，因为 最后的大小不一定大于 最后的大小。于是我们让操作次数为：最小的大于 的值，最后再向前回溯。容易证明回溯的次数不超过 。

一些细节就写在注释里面了。

参考代码（细节很多）

#include <map>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define int long long
#define LL long long
template <typename T>
void read (T &x) {
    x = 0; T f = 1;
    char ch = getchar ();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar ();
    }
    x *= f;
}
template <typename T>
void write (T x) {
    if (x < 0) {
        putchar ('-');
        x = -x;
    }
    if (x < 10) {
        putchar (x + '0');
        return;
    }
    write (x / 10);
    putchar (x % 10 + '0');
}
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }

const int Maxn = 1e6;
const LL Maxr = 1e18;

int n;
LL k, p;
LL a[Maxn + 5], tema[Maxn + 5];
//tema用于存储原数组 

bool check (LL x) {
    LL temp = a[n] - x * p;//最后a[n]的大小
    LL sum = 0;//统计需要操作多少次
    for (int i = 1; i <= n; i++) {
        if (a[i] <= temp) continue;//排名在 [idx, n]
        sum += (a[i] - temp) / p;
    }
    return sum >= k;//当操作次数大于k时满足要求 
}
struct Node {
    int idx;
    LL val;
    Node () {}
    Node (int IDX, LL VAL) {
        idx = IDX;
        val = VAL;
    }
};
bool operator < (Node x, Node y) {
    return x.val > y.val;
}
priority_queue <Node> q;
void solve (LL x) {
    LL temp = a[n] - x * p;//原a[n]最后的大小 
    LL sum = 0;//需要的操作次数 
    for (int i = 1; i <= n; i++) {
        if (a[i] < temp) continue;
        //元素的最后排名在 [idx, n) 里我们才会统计操作次数并且才可能会回溯 
        sum += (a[i] - temp) / p;
        a[i] -= (a[i] - temp) / p * p;
        q.push (Node (i, a[i]));
    }
    for (int i = 1; i <= sum - k; i++) {
        Node tem = q.top (); q.pop ();
        while (a[tem.idx] + p > tema[tem.idx]) {
            //有两点细节 
            //1.(83~92)行不能改成下面的代码
            //if (a[tem.idx] + p > tema[tem.idx]) continue
            //因为continue之后回溯的步数就会少1(不妨手推一下) 
            //(我考试时就是这里没调出来) 
            //2.tem.idx也不是可以无限加下去的，Ta不能超过原元素的大小 
            //(这个点让我对拍+调试了1h+) 
            tem = q.top (); q.pop ();
        }
        a[tem.idx] += p; 
        tem.val += p;
        q.push (tem);
        //(93~95)行都是回溯 
    }
    sort (a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        write (a[i]); putchar (' ');
    }
}

signed main () {
    read (n); read (k); read (p);
    for (int i = 1; i <= n; i++) {
        read (a[i]);
    }
    sort (a + 1, a + 1 + n);
    memcpy (tema, a, sizeof a);

    if (p == 0) {//等于0时，除数就为0了，需要特判 
        for (int i = 1; i <= n; i++)
            printf ("%lld ", a[i]);
        return 0;
    }

    LL l = 0, r = Maxr * 2 / p;
    //二分，最后的 a[n] 为 a[n] - mid * p 
    while (l + 1 < r) {
        LL mid = l + r >> 1;
        if (check (mid)) r = mid;
        else l = mid;
    }
    if (check (l)) solve (l);
    else solve (r);
    return 0;
}