题解：P12149 【MX-X11-T3】「蓬莱人形 Round 1」科学

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
ll a[400010];
ll b[400010], w[400010];
PII pt[400010];
int n, m;
vector<ll> wt_ball; // 待匹配
vector<PII> box;
// value id
ll V = 0;
ll ans2 = 0x3f3f3f3f3f3f3f3f;
priority_queue<ll, vector<ll>, greater<ll> >hp;

ll check(ll mid) {
	wt_ball.clear();
	box.clear();
	hp = (priority_queue<ll, vector<ll>, greater<ll> >) {};
	for (int i = 1; i <= n; i++) {
		if (a[i] > mid)
			wt_ball.push_back(a[i] - mid);
		if (a[i] <= mid) {
			wt_ball.push_back(a[i]);
			box.push_back({mid, 0ll});
		}
	}
	for (int i = 1; i <= m; i++) {
		box.push_back({min(mid, b[i]), w[i]});
	}
	sort(wt_ball.begin(), wt_ball.end());
	sort(box.begin(), box.end());
	ll cnt = 0ll;
	int j = box.size() - 1;
	for (int i = wt_ball.size() - 1; i >= 0; i--) {
		while (j >= 0 && box[j].first >= wt_ball[i]) {
			hp.push(box[j].second), j--;
		}
		if (hp.size() == 0) {
			return 0;
		}
		cnt += hp.top();
		hp.pop();
	}
//	printf("===%lld %lld\n", mid, cnt);
	return cnt;
}

signed main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]), V = max(V, a[i]);
	for (int i = 1; i <= m; i++) {
		ll x, y;
		scanf("%lld%lld", &x, &y);
		b[i] = x, w[i] = y;
	}
	ll l = 1, r = V;
	while (l < r) {
		ll mid = (l + r) / 2;
		ll t = check(mid);
		if (t)
			r = mid, ans2 = t;
		else
			l = mid + 1;

	}
	printf("%lld %lld", r, check(r));
	return 0;
}