zoj 3410 Layton's Escape

Layton's Escape

---

Time Limit: 2 Seconds      Memory Limit: 65536 KB

---

Professor Layton is a renowned archaeologist from London's Gressenheller University. He and his apprentice Luke has solved various mysteries in different places.

Unfortunately, Layton and Luke are trapped in a pyramid now. To escape from this dangerous place, they need to pass N traps. For each trap, they can use Ti minutes to remove it. If they pass an unremoved trap, they will lose 1 HP. They have K HP at the beginning of the escape and they will die at 0 HP.

Of course, they don't want trigger any traps, but there is a monster chasing them. If they haven't pass the ith trap in Di minutes, the monster will catch and eat them. The time they start to escape is 0, and the time cost on running will be ignored. Please help Layton to escape from the pyramid with the minimal HP cost.

Input

There are multiple test cases (no more than 20).

For each test case, the first line contains two integers N and K (1 <= N <= 25000, 1 <= K <= 5000), then followed by N lines, the ith line contains two integers Ti and Di (0 <= Ti <= 10^9, 0 <= Di <= 10^9).

Output

For each test case, if they can escape from the pyramid, output the minimal HP cost, otherwise output -1.

Sample Input

3 2
40 60
60 90
80 120
2 1
30 120
60 40

Sample Output

1
-1

总结一下，这道题目比赛的时候本来想到做法了，但是……还是没有想太清楚，总觉得有点儿不对，以为很困难的样子，然后就没有往下想，后来才知道，就是那么做的，贪心的做法。
首先，要注意，所有陷阱不一定要一次通过，也就是不是那种一关一关地通的那种，也就是说可以随意选择先走哪个，再走哪个。
做法就是先把每一关怪物到来的时间从小到大排序，又用到了结构体的一级排序。要记住：

struct seg{
  int a, b;
  friend bool operator < (seg x, seg y){
    return x.a < y.a;
  }
}x[25000+10];
int cmp(const void *x, const void *y){
  return (*(seg*)x).b - (*(seg*)y).b;
}

这个就是按照结构体中的变量 b 从小到大排序。然后呢，就是建一个优先队列，为什么用优先队列捏？原因很简单，因为想法就是当遇到一个不能通过的关卡是，我要损失一滴血，跳过其中的一关，那到底跳过哪一关捏？当然是跳过花费自己的时间最长的那一关啊，所以优先队列的作用就是把通过每一关需要花费的时间从大到小排序，这样跳过每一关的时候，只需要pop一个元素就可以了，实际上，当初自己就是这个地方没有想透彻，以为跳过其中一关后可能影响已经通过的其他的关卡的通过与否，事实上，这是不影响的，只要跳过已经通过的当中花费时间最长的那一关，就一定可以通过除了这一关之外的已经通过的所有关卡，包括正在通过的这一关。这样就OK了，另外，还有一个细节，就是当血的数量为0的时候，失败，输出-1，所以，当决定跳过一关的时候，要判断血的数量是不是大于1，而不是大于0！这个边界条件要搞清楚。

结构体中的friend友元函数，目的是构造优先队列的时候，按照变量 a 的值从大到小排序，方便以后出队。

学习了一下优先队列，这题WA了一次……

原来是水题啊，唉。

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct seg{
  int a, b;
  friend bool operator < (seg x, seg y){
    return x.a < y.a;
  }
}x[25000+10];
int cmp(const void *x, const void *y){
  return (*(seg*)x).b - (*(seg*)y).b;
}
int main(void){
  int n, k;
#ifndef ONLINE_JUDGE
  freopen("zoj3410.in", "r", stdin);
#endif
  while (~scanf("%d%d", &n, &k)){
    int sum = 0, temp = k; bool flag = true;
    priority_queue<seg> p;
    for (int i = 0; i < n; ++i){
      scanf("%d%d", &x[i].a, &x[i].b);
    }
    qsort(x, n, sizeof(x[0]), cmp);
    for (int i = 0; i < n; ++i){
      if (!flag) break;
      sum += x[i].a; p.push(x[i]);
      if (sum <= x[i].b){
      }
      else {
        if (p.size() != 0 && k > 1){
          sum -= p.top().a; p.pop(); k--;
        }
        else{
          flag = false;
        }
      }
    }
    if (flag) printf("%d\n", temp - k);
    else printf("-1\n");
  }
  return 0;
}

没看别人的解题报告……自己做的，有成就感，O(∩_∩)O哈哈~

学习优先队列的测试程序：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;
struct seg{
  int a, b;
  friend bool operator < (seg x, seg y){
    return x.a > y.a;
  }
}ti[30];
int main(void){
  freopen("priority.in", "r", stdin);
  priority_queue<seg> q;
  queue<seg> p;
  for (int i = 0; i < 3; ++i)
  {
    scanf("%d%d", &ti[i].a, &ti[i].b);
    q.push(ti[i]); p.push(ti[i]);
  }
  for (int i = 0; i < 3; ++i) 
  {printf("%d %d ", q.top().a, q.top().b); q.pop();printf("\n");}
  printf("\n");
  for (int i = 0; i < 3;++i) 
  {printf("%d %d ", p.front().a, p.front().b); p.pop(); printf("\n");}
  printf("\n");
  return 0;
}

priority.in文件：

40 60
80 90
60 120

输出：

40 60
60 120
80 90

40 60
80 90
60 120

Hit any key to close this window...

^_^