爱悠闲 > ZJU 3433 Gu Jian Qi Tan 贪心 优先队列

ZJU 3433 Gu Jian Qi Tan 贪心 优先队列

分类: 题解  |  标签: 算法  |  作者: swordholy 相关  |  发布日期 : 2014-05-12  |  热度 : 29°

跟前一次月赛的算法类似,能打就打,不能打就用当前的替换原来打过的花费最大的怪,贪心好题,开始往DP上想了好久,复杂度怎么都降不下来,贪心才是王道啊。

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<queue>

using namespace std;

int spe[1005][1005];

int add[1005];

bool fl;

priority_queue<int> p;

int main()

{

int t,n,i,j,x,ans,now;

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

for(i=1;i<=n;i++)

{

scanf("%d",&spe[i][0]);

for(j=1;j<=spe[i][0];j++)

scanf("%d",&spe[i][j]);

}

for(i=1;i<=n;i++)

scanf("%d",&add[i]);

   now=0;

while(!p.empty()) p.pop();

for(i=1;i<=n;i++)

{

            now+=add[i];

for(j=1;j<=spe[i][0];j++)

if ((now>=spe[i][j]))

 {

 now-=spe[i][j];

 p.push(spe[i][j]);

 }

else

if(!p.empty()&&(p.top()>=spe[i][j]))

{

now+=p.top()-spe[i][j];

                        p.pop();

p.push(spe[i][j]);

}

}

printf("%d/n",p.size());

}

}