怎么创建自己公司的网站_做网站找哪个软件_南京seo外包平台_2022年国际十大新闻

题目链接

AtCoder Beginner Contest 373 E

思路

很明显，答案是具有单调性的，我们考虑二分答案。

我们定义$s$数组为$a$数组从大到小排序后的前缀和数组。

对于排序后的第$i$个数，我们假设给其增加$x$票（通过二分答案确定），若是想要其当选，则将剩下的$k-x$票给其他候选者之后，比$a[i]+x$多的不得大于$m$个。

因此我们可以在前缀和数组上再次二分，直接判断$x$是否可行即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int b[N], s[N];
struct node
{int a, id, ans;
} p[N];
void solve()
{cin >> n >> m >> k;for (int i = 1; i <= n; i++){cin >> p[i].a;p[i].id = i;k -= p[i].a;}sort(p + 1, p + 1 + n, [&](node x, node y) {return x.a > y.a;});for (int i = 1; i <= n; i++){s[i] = s[i - 1] + p[i].a;b[i] = p[n - i + 1].a;}for (int i = 1; i <= n; i++){if (p[i].a == p[i - 1].a){	//特殊情况p[i].ans = p[i - 1].ans;continue;}if (p[i].a + k < p[m].a){p[i].ans = -1;continue;}if (i <= m){int res = (m + 1 - i) * p[i].a - (s[m + 1] - s[i]) + (m + 1 - i);if (res > k)p[i].ans = 0;else{int low = 1, high = k;while (low < high){int mid = low + high >> 1;auto check = [&](auto check, int x)->bool{int op = p[i].a + x;int tmpk = k - x;int idx = upper_bound(b + 1, b + 1 + n, op) - b;idx = n - idx + 1;int res = (m + 1 - idx - 1) * op - (s[m + 1] - s[idx]) + p[i].a + (m + 1 - idx - 1);return res <= tmpk;};if (check(check, mid)){low = mid + 1;}else high = mid;}p[i].ans = high;}}else{int low = 1, high = k;while (low < high){int mid = low + high >> 1;auto check = [&](auto check, int x)->bool{int op = p[i].a + x;int tmpk = k - x;int idx = upper_bound(b + n - m + 1, b + 1 + n, op) - b;idx = n - idx + 1;int res = (m - idx) * op - (s[m] - s[idx]) + (m - idx);return res <= tmpk;};if (check(check, mid)){low = mid + 1;}else high = mid;}p[i].ans = high;}}sort(p + 1, p + 1 + n, [&](node x, node y) {return x.id < y.id;});for (int i = 1; i <= n; i++){cout << p[i].ans << " ";}cout << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}