E - Handshake

2024-08-28 12:20

文章标签 handshake

本文主要是介绍E - Handshake，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

就是二分再二分的题目。。
中规中矩吧。。
题目链接

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int  n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;
int sum[N];
void solve() {cin >> n >> m;int a[n];for (int &x : a)cin >> x ;sort(a, a + n);//这边正序排就好了。下面lower_bound方便点for (int i = 0; i < n; ++i) {sum[i + 1] = sum[i] + a[i];}function<ar(int)> ok = [&](int mx) ->ar{// 就是要枚举右端点。。然后算 左边和特匹配的有多少个>=mxint cnt = 0, ans = 0;//sum 和 有效个数for (int i = 0; i < n; ++i) {if (a[i] + a[n - 1] < mx)continue;int j = lower_bound(a, a + n, mx - a[i]) - a ;cnt += n - j;ans += sum[n] - sum[j] + a[i] * (n - j);}if (cnt >= m)return {ans, cnt};elsereturn { -1, 0};};int l = 0, r = inf;while (l < r) {int mid = (l + r + 1) >> 1;if (ok(mid)[0] != -1)l = mid;elser = mid - 1;}auto[all, cnt] = ok(l);cout << all - (cnt - m)*l;};// 为什么这题会是蓝题。。
// 实际上还是有点东西的。。
// 比如 怎么统计个数啊。。算all啊。。
// 怎么证明最后那部分都是l     5 4 3 3 3 3 后面多出来部分都是3 。。 如果不是3的话。。那就会被截取掉。。signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}