基本思路是二分答案,自认为写的没问题,我的问题是本地vscode和在线对样例的评测结果不同。
#include <iostream> #include <algorithm> using namespace std; int N, M, K, A[105] = {0}, B[105]; bool cmp(int a, int b) { return a > b; } void copy() { for (int i = 1; i <= M; i++) { B[i] = A[i]; } } bool P(int x) { int cnt = 0; for (int i = 1; i <= M; i++) { if (B[i] > x) cnt += B[i] - x; } if (cnt > K) return false; for (int i = 2; i <= M; i++) { if (B[i] > x) cnt += x; else cnt += B[i]; if (cnt >= K) return true; } return false; } int solve(int i) { copy(); B[i] = 0; int ans; sort(B + 1, B + 1 + M, cmp); int l = 0, r = B[1]; while (l <= r) { int mid = (l + r) >> 1; if (P(mid)) ans = mid, r = mid - 1; else l = mid + 1; } return ans; } int main() { cin >> N >> M >> K; int tmp; for (int i = 1; i <= N; i++) { cin >> tmp; A[tmp]++; } for (int i = 1; i <= M - 1; i++) { if (N - A[i] < K) cout << -1 << ' '; else cout << solve(i) << ' '; } if (N - A[M] < K) cout << -1 << ' '; else cout << solve(M); }
以上是代码。
对第二个测试样例:
本地运行结果为:1 0 -1
而在网站上自测运行结果为:1 1 -1
这是为什么?
全部评论
(0) 回帖