2010-1156

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by 猛犸也钻地

解题报告：

{{{
这题给出M个迷宫，在第i个迷宫中，你可以获得A[i]个Cake，并有许多Ice Heart(IH)，对于第j个IH可以靠消耗B[i][j]个Cake来获得。
最后，要求按顺序走完全部迷宫后，最多能获得多少IH。

这题可以采用贪心策略，走到一个迷宫后，尽可能地占下所有的IH，如果占下某个IH时将当前积累的Cake消耗成了负数，则放弃之前取得的一个消耗Cake最大的IH。
}}}


代码：

{{{
#include <cstdio>
#include <queue>
using namespace std;

int a[1000],b[1000][1000];

int main(){
    int t,m,n;
    scanf("%d",&t);
    while(t--){
        priority_queue<int> q;
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&a[i]);
            for(int j=0;j<a[i];j++) scanf("%d",&b[i][j]);
        }
        int v,s=0;
        for(int i=0;i<m;i++){
            scanf("%d",&v);
            s+=v;
            for(int j=0;j<a[i];j++){
                s-=b[i][j];
                q.push(b[i][j]);
                if(s<0){
                    s+=q.top();
                    q.pop();
                }
            }
        }
        printf("%d\n",q.size());
    }
}
}}}

by 猛犸也钻地

解题报告：

这题给出M个迷宫，在第i个迷宫中，你可以获得A[i]个Cake，并有许多Ice Heart(IH)，对于第j个IH可以靠消耗B[i][j]个Cake来获得。
最后，要求按顺序走完全部迷宫后，最多能获得多少IH。
这题可以采用贪心策略，走到一个迷宫后，尽可能地占下所有的IH，如果占下某个IH时将当前积累的Cake消耗成了负数，则放弃之前取得的一个消耗Cake最大的IH。

代码：

#include <cstdio>
#include <queue>
using namespace std;
int a[1000],b[1000][1000];
int main(){
    int t,m,n;
    scanf("%d",&t);
    while(t--){
        priority_queue<int> q;
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&a[i]);
            for(int j=0;j<a[i];j++) scanf("%d",&b[i][j]);
        }
        int v,s=0;
        for(int i=0;i<m;i++){
            scanf("%d",&v);
            s+=v;
            for(int j=0;j<a[i];j++){
                s-=b[i][j];
                q.push(b[i][j]);
                if(s<0){
                    s+=q.top();
                    q.pop();
                }
            }
        }
        printf("%d\n",q.size());
    }
}