poj 2431 Expedition (贪心)

传送门

解题思路

　　用堆贪心，每次能走就走，不能走从大根堆里取出以前加进去的油量并更新答案。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;
const int MAXN = 10005;

inline int rd(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return f?x:-x;
}

int n,l,p,ans,oil;
struct Data{
	int dis,w;
	friend bool operator<(const Data A,const Data B){
		return A.dis>B.dis;
	}
}data[MAXN];
priority_queue<int> Q;

int main(){
	n=rd();
	for(int i=1;i<=n;i++)
		data[i].dis=rd(),data[i].w=rd();
	sort(data+1,data+1+n);data[n+1].dis=0;
	l=rd();p=rd();int res=p;
	for(int i=1;i<=n+1;i++){
		data[i].dis=l-data[i].dis;
		int DIS=data[i].dis-data[i-1].dis;
		if(DIS<=res) {res-=DIS;Q.push(data[i].w);continue;}
		while(Q.size()){
			ans++;res+=Q.top();Q.pop();
			if(res>=DIS) break;
		}
		if(!Q.size() && res<DIS) {puts("-1");return 0;}
		res-=DIS;Q.push(data[i].w);
	}
	cout<<ans;
	return 0;
}