【反悔贪心】求问题解中为何都写<=q.size()
查看原帖
【反悔贪心】求问题解中为何都写<=q.size()
932978
Twinkling楼主2024/1/28 17:04

代码中已标示,认为在本题中,q.size()最多与a[i].d相等,为何大多数题解中都写的是a[i].d <= (int)q.size()

关键的是我改成等号可以AC。。。

求助dalao中QWQ

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define int long long
int n;
struct node{
	int d,p;
}a[N],tmp;
bool cmp(node x,node y){
	return (x.d < y.d);
}
priority_queue<int,vector<int>,greater<int> >q;

int ans;
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i].d >> a[i].p;
	}
	sort(a+1,a+1+n,cmp);
	tmp = a[1];
	for(int i = 1; i <= n; i++){
 		if(a[i].d == (int)q.size()){//???
			if(q.top() < a[i].p){
				ans += a[i].p - q.top();
				q.pop();
				q.push(a[i].p);
			}
		}
		else{
			ans += a[i].p;
			q.push(a[i].p);
		}
	}
	cout << ans << endl;
	return 0;
}

2024/1/28 17:04
加载中...