WA 50 pts 求调!
查看原帖
WA 50 pts 求调!
878013
_Supernova楼主2024/8/7 09:05
//反悔贪心 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
const int N = 1e5 + 5;
int n;
struct work {
	int d; // 截止时间 
	int p; // 利润
} w[N];
ll ans;
bool cmp_work(work a, work b) {
	return a.d < b.d;
}
priority_queue <int, vector <int>, greater <int> > q;
int main(void) {
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> w[i].d >> w[i].p;
	}
	sort(w + 1, w + n + 1, cmp_work);
	for (int i = 1; i <= n; ++i) {
		if (w[i].d <= (int)q.size() && w[i].p > q.top()) {
			ans -= (ll)q.top();
			q.pop();
			ans += (ll)w[i].p;
			q.push(w[i].p);
		} 
		else {
			ans += (ll)w[i].p;
			q.push(w[i].p);
		}
	}
	cout << ans;
    return 0;
}
2024/8/7 09:05
加载中...