csdn
題面
1.前言
我考試時把全部時間都交給這道題（T3）了，結果還沒調出來，最後發現 自己是傻逼 自己又出現了傻逼錯誤，我真的是傻逼。為了警戒自己注意細節，于是寫下了這篇題解
2.題解
現将
a
a
a 數組排序，可以考慮二分。二分什麼呢？答曰：二分答案。
當然，不是集合中的每個元素都要二分答案，我們隻二分原來還沒有開始操作時最大的元素(
a
[
n
]
a[n]
a[n])最後的大小。
我們假設
a
[
n
]
a[n]
a[n] 最後的大小排名第
i
d
x
idx
idx，不妨假設原
[
i
d
x
,
n
)
[idx, n)
[idx,n) 的元素最後的排名分布在
(
i
d
x
,
n
]
(idx, n]
(idx,n]。
容易證明，當
a
[
n
]
a[n]
a[n] 最後的大小越小，需要操作的次數越多。
c
h
e
c
k
check
check 函數就很好寫了
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時滿足要求
}
但還沒完，我們還需要對它進行一定的調整，因為
a
[
i
]
(
i
∈
[
i
d
x
,
n
)
)
a[i] (i \in [idx, n))
a[i](i∈[idx,n)) 最後的大小不一定大于
a
[
n
]
a[n]
a[n] 最後的大小。于是我們讓操作次數為最小的大于
k
k
k 的值，最後再向前回溯。容易證明回溯的次數不超過
O
(
n
)
O(n)
O(n)。
一些細節就寫在注釋裡面了。
參考代碼（細節很多）
#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;
}
3.小結
平時太依賴于評測機和資料了，一會改不出來就去下資料，平時的散漫就導緻考試時要求有限的時間時，就不能很快的跳出來。
之後我一定要改正，不然就會像今天這樣，有思路但是打不出來，細節考慮不到，令人唏噓，後悔不盡。