【题目大意】:一个人有k滴血,要逃出一个有n个陷阱的地方,面对每个陷阱有两个处理方式:1是直接过去,损失1滴血;2是花费ti的时间去搞定这个陷阱,自己平安过去。另外,如果超过di的时间,尚未离开这个陷阱就会被怪物吃掉。问安全的过掉陷阱后最少花费多少滴血,不能通过输出-1;
【解题思路】:一开始以为陷阱是必须按照一定的顺序来穿过的,把其当成了dp来处理,后来发现,其实,陷阱是可以随机选择的,因此,我们只需要按照di先进行排序,然后在di相同的情况先对ti进行排序。之后,我们每一次的处理就是先走那些会先被怪物追上的陷阱,然后当发现某个陷阱无法在规定时间内通过的时候,我们就需要用将其越过的陷阱所花费的最大时间去掉再判断即刻。这里须维护一个优先队列来优化。
【代码】:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n,k,ans;
struct Node
{
int ti,di;
bool operator <(const Node &b) const{
return ti < b.ti;
}
}d[26000];
priority_queue<Node> q;
bool cmp(const Node &a, const Node &b){
return (a.di < b.di) || (a.di==b.di && a.ti < b.ti);
}
void solve(){
while (!q.empty()) q.pop();
int tot=0;
for (int i=0; i<n; i++){
q.push(d[i]);
if (tot+d[i].ti<=d[i].di){
tot+=d[i].ti;
}
else{
while (tot+d[i].ti>d[i].di && !q.empty()){
Node tmp=q.top();
q.pop();
tot-=tmp.ti;
k--;
ans++;
if (k<=0) {ans=-1; return ;}
}
tot+=d[i].ti;
}
}
return ;
}
int main(){
while (scanf("%d%d",&n,&k)!= EOF){
for (int i=0; i<n; i++) scanf("%d%d",&d[i].ti,&d[i].di);
sort(d,d+n,cmp);
ans=0;
solve();
printf("%d\n",ans);
}
return 0;
}