Solution - P2748 [USACO16OPEN]Landscaping P

Posted on Edited on

P2748 [USACO16OPEN]Landscaping P

idea:

带悔贪心

解决方案

讲不灵清，见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans,n,c[2],Z;
signed main(){
	priority_queue< int,vector<int>,greater<int> > q[2];
	cin>>n>>c[0]>>c[1]>>Z;
	for (int i=1;i<=n;++i){
		int a,b;cin>>a>>b;a=a-b;
		for (int j=1;j<=abs(a);++j){
			while (q[a<0].size()&&q[a<0].top()+Z*i>=c[a>0]) q[a<0].pop();
			if (!q[a<0].size()) q[a>0].push(-c[a>0]-Z*i),ans+=c[a>0];
			else{
				q[a>0].push(-q[a<0].top()-Z*i-Z*i);
				ans+=q[a<0].top()+Z*i;q[a<0].pop();
			}
		}
	}
	return cout<<ans,0; 
}