首先,这份代码是可以 AC 的:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
inline int read() {
int w = 1, q = 0; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
return w * q;
}
struct node {
int w, id;
}a[N];
bool cmp(node x, node y) {
return x.w > y.w;
}
int b[N], s[N], rk[N], rks[N], ans[N];
signed main() {
int c, n, k;
c = read(), n = read(), k = read();
for (int i = 1; i <= n; i++)
a[i].w = read(), a[i].id = i, b[i] = a[i].w;
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i].w;
for (int i = 1; i <= n; i++) {
int j = i; rk[i] = i;
while (a[j + 1].w == a[i].w) rk[++j] = i;
i = j;
rks[i] = j;
}
for (int i = 1; i <= n; i++) {
if (rk[i] >= k) ans[a[i].id] = a[rks[k]].w - a[i].w;
else if (rks[rk[i]] < k) ans[a[i].id] = (k - i) * a[i].w - s[k] + s[i];
}
for (int i = 1; i <= n; i++)
cout << ans[i] << "\n";
return 0;
}
但是,对于以下这组数据,它输出了错误的答案:
input:
0 5 2
1 1 2 2 2
output:
-1
-1
0
0
0
更改过后的代码如下:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
inline int read() {
int w = 1, q = 0; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
return w * q;
}
struct node {
int w, id;
}a[N];
bool cmp(node x, node y) {
return x.w > y.w;
}
int b[N], s[N], rk[N], rks[N], ans[N];
signed main() {
int c, n, k;
c = read(), n = read(), k = read();
for (int i = 1; i <= n; i++)
a[i].w = read(), a[i].id = i, b[i] = a[i].w;
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + a[i].w;
for (int i = 1; i <= n; i++) {
int j = i; rk[i] = i;
while (a[j + 1].w == a[i].w) rk[++j] = i;
i = j;
rks[i] = j;
}
for (int i = 1; i <= n; i++) {
if (rk[i] >= k) ans[a[i].id] = a[k].w - a[i].w;//rks[k] -> k
else if (rks[rk[i]] < k) ans[a[i].id] = (k - i) * a[i].w - s[k] + s[i];
}
for (int i = 1; i <= n; i++)
cout << ans[i] << "\n";
return 0;
}
可以输出正确答案:
1
1
0
0
0
所以数据是否过水?(经测试,并没有一组数据相同的 ai 的出现次数大于 2)还有拜托大佬看看上面这份代码还有没有什么问题。
顺便提一嘴,原代码中的这一部分一开始我写错了:
for (int i = 1; i <= n; i++) {
int j = i; rk[i] = i;
while (a[j + 1].w == a[i].w) rk[++j] = i-1;//这里写成了 i-1
i = j;
rks[i] = j;
}
同样可以 AC。