crystal 题解
2026-11-09 18:20:25
发布于:江西
15阅读
0回复
0点赞
题意:
你有 次操作,每次选择一个下标 ,给 加
求最多相同的数的个数
首先你可以注意到,那个相同的数 ( 后记为 ) 一定可以是某个
为什么?我们可以思考一下
假设这个 是最优的,且它不在 里,那么 一定是 不劣 的(此处请读者自行思考)
假如 不在 里,那么我们还可以推出 不劣 等
这样递降, 总是在 里
考虑枚举
假如你选择了某一个 作为 ,显然只有 的数可以被增加到 ,如何快速的找到这些数?
有一个办法:排序
而且你会发现,要想使 成为 ,需要花费 步,你要尽可能多的选择,而排序了之后,从 贪心是最优的
此时你便可以写出 代码:
#include <bits/stdc++.h>
int main()
{
long long N, m;
std:: cin >> N >> m;
std:: vector<long long> arr(N + 1);
for (int i = 1; i <= N; ++i)
{
std:: cin >> arr[i];
}
std:: sort(arr.begin() + 1, arr.end());
long long res = 0;
for (int i = 1; i <= N; ++i)
{
// 让其他的水晶尝试成为a_i
long long sum = 0, ct = 0;
for (int j = i; j > 0; --j)
{
sum += arr[i] - arr[j];
if (sum <= m)
{
++ct;
} else break;
}
res = std:: max(res, ct);
}
std:: cout << res << '\n';
return 0;
}
继续考虑优化,你从后往前贪心,一定是个区间
可以去尝试推公式:
后面部分可以使用前缀和优化,这样,我们就能 求出一个区间需要的步数
注意到定 时,答案具有单调性,使用二分,然后,你就可以解决这一题目
代码:
#include <bits/stdc++.h>
int main()
{
long long N, m;
std:: cin >> N >> m;
std:: vector<long long> arr(N + 1), pre(N + 1);
for (int i = 1; i <= N; ++i)
{
std:: cin >> arr[i];
}
std:: sort(arr.begin() + 1, arr.end());
for (int i = 1; i <= N; ++i)
{
pre[i] = pre[i - 1] + arr[i];
}
long long res = 0;
for (int i = 1; i <= N; ++i)
{
// 让其他的水晶尝试成为a_i
long long l = 1, r = i, ans = -1;
while (l <= r)
{
long long mid = (l + r) / 2;
if ((i - mid) * arr[i] - pre[i - 1] + pre[mid - 1] <= m)
{
ans = i - mid + 1;
r = mid - 1;
} else l = mid + 1;
}
res = std:: max(res, ans);
}
std:: cout << res << '\n';
return 0;
}
这里空空如也





有帮助,赞一个