独立博客: 哲学与程序

哲学与程序

ZOJ@3433

ZOJ@3433
题意:m个按序迷宫,每个迷宫可收集一定数量的cake,迷宫中的BOSS有n个ice heart,每一个需消耗的一定cake才能获得,问通过这m个迷宫,可拿多少ice heart。
解法:贪心。对于一个ice heart,如果当前cake数大于或等于该ice heart的消耗,则直接取得,如果不,则用前面消耗的最大cake的与当前ice heart比较,当前ice heart消耗小些,则交换,赚一点cake,否则不换。用一个最大堆维护即可。
// 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;
}


posted on 2011-01-15 21:44 哲学与程序 阅读(186) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序