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
Sample Output
标题:ピラミッドを通る人がいますが、多くの罠があります.彼は罠を通らなければなりません.罠を通るたびにti時間がかかりますが、後ろに怪物がいます.彼らを追いかけています.もしいつもdiを超える時間があれば、彼らは少し精力を費やす必要があります.精力が0になると、彼らは死んでしまいます.この人がピラミッドを通ることができるかどうかを求めます.通過できるのは、少なくともどれだけの精力が必要なのか.
欲張り+優先キューは、時間を超えると最小限に抑えるのが一番で、優先キューを使う必要があります.
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
标题:ピラミッドを通る人がいますが、多くの罠があります.彼は罠を通らなければなりません.罠を通るたびにti時間がかかりますが、後ろに怪物がいます.彼らを追いかけています.もしいつもdiを超える時間があれば、彼らは少し精力を費やす必要があります.精力が0になると、彼らは死んでしまいます.この人がピラミッドを通ることができるかどうかを求めます.通過できるのは、少なくともどれだけの精力が必要なのか.
欲張り+優先キューは、時間を超えると最小限に抑えるのが一番で、優先キューを使う必要があります.
#include
#include
#include
#include
#include
#include
using namespace std;
struct point
{
long long t;
long long d;
}p[25002];
bool cmp(point a,point b)
{
if(a.d==b.d)
return a.tq;
for(i=0;ip[i].d)
{
tt++; T-=q.top();
q.pop();
}
//cout<=k)
printf("-1
");
else
printf("%d
",tt);
}
return 0;
}