题意:从起点驾车出发到距离为m的城镇,初始油量为k,油箱容量无穷大,途中有(n(n<=10000))个加油站,每个加油站给定其与城镇的距离和油量.每个距离单位花费油量为1.求最少要加几次油?
分析:贪心题:不断往城镇走,如果油量不足,则选择已经经过的加油站中油量最多的加油.
具体来说,求出每个加油站与起点的距离,把最后的城镇也看成一个油量为0,距离起点为m的加油站.然后把这些加油站按照距离从小到大排序.从1号开始枚举,如果当前油量能够走到当前枚举到的城镇,则不用加油.否则选择之前最大油量的加油(zhege借助大根堆来维护即可).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=10005;
struct node{int dis,val;}a[N];
inline bool cmp(node x,node y){return x.dis<y.dis;}
int main(){
int T=read();
while(T--){
int n=read();
for(int i=1;i<=n;++i){
a[i].dis=read();
a[i].val=read();
}
int m=read(),k=read();
for(int i=1;i<=n;++i)a[i].dis=m-a[i].dis;
a[++n].dis=m;a[n].val=0;//把城镇看做n+1号加油站
sort(a+1,a+n+1,cmp);//按照距离从小到大排序.
priority_queue<int>q;while(q.size())q.pop();//大根堆,多组数据初始化
int res=k,now=0,bj=1,ans=0;
//res当前剩余油量,now当前位置,ans是加油次数
for(int i=1;i<=n;++i){
int Need=a[i].dis-now;
while(res<Need){//如果当前油量不够
if(q.empty()){//没油了,无法到达
puts("-1");
bj=0;break;
}
res+=q.top();q.pop();
++ans;
}
if(!bj)break;
res-=Need;
now=a[i].dis;
q.push(a[i].val);
}
if(bj)printf("%d
",ans);
}
return 0;
}