数据过水?
查看原帖
数据过水?
731925
happy_zero楼主2023/8/27 22:19

首先,这份代码是可以 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

所以数据是否过水?(经测试,并没有一组数据相同的 aia_i 的出现次数大于 22)还有拜托大佬看看上面这份代码还有没有什么问题。

顺便提一嘴,原代码中的这一部分一开始我写错了:

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。

2023/8/27 22:19
加载中...