ZOJ@3433題意：m個(gè)按序迷宮，每個(gè)迷宮可收集一定數(shù)量的cake，迷宮中的BOSS有n個(gè)ice heart，每一個(gè)需消耗的一定cake才能獲得，問(wèn)通過(guò)這m個(gè)迷宮，可拿多少ice heart。
解法：貪心。對(duì)于一個(gè)ice heart，如果當(dāng)前cake數(shù)大于或等于該ice heart的消耗，則直接取得，如果不，則用前面消耗的最大cake的與當(dāng)前ice heart比較，當(dāng)前ice heart消耗小些，則交換，賺一點(diǎn)cake，否則不換。用一個(gè)最大堆維護(hù)即可。
// 2386805 2011-01-15 21:33:57 Accepted 3433 C++ 350 4100 redsea
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
using namespace std;
struct laby
{
int n;
int cake;
int sp[1001];
}l[1001];
int m;
struct Node
{
int cake;
bool operator < (struct Node a)const
{
return cake < a.cake;
}
};
void solve()
{
priority_queue<struct Node>Heap;
struct Node tmp;
int cake = 0;
int ans = 0;
for(int i = 1; i <= m; i++)
{
cake += l[i].cake;
for(int j = 0; j < l[i].n; j++)
{
if(cake >= l[i].sp[j])
{
ans++;
cake -= l[i].sp[j];
tmp.cake = l[i].sp[j];
Heap.push(tmp);
}else{
if(!Heap.empty())
{
tmp = Heap.top();
if(tmp.cake > l[i].sp[j]){
cake += tmp.cake;
ans--;
Heap.pop();
}
}
if(cake >= l[i].sp[j])
{
ans++;
cake -= l[i].sp[j];
tmp.cake = l[i].sp[j];
Heap.push(tmp);
}
}
}
}
printf("%d\n",ans);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&m);
for(int i = 1; i <= m; i++){
scanf("%d",&l[i].n);
for(int j = 0; j < l[i].n; j++){
scanf("%d",&l[i].sp[j]);
}
}
for(int i = 1; i <= m; i++)
{
scanf("%d",&l[i].cake);
}
solve();
}
return 0;
}