zoj 3410 Layton's Escape

March 21, 2013
zoj

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. 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). For each test case, if they can escape from the pyramid, output the minimal HP cost, otherwise output -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...

^_^

Read more