hdu-4415-Assassin’s Creed

/*一个想法题，思路是：先把各个剑次数，分成0和非0两类，在非零的哪一类，只要杀一个那么所有的都可以杀完，下面分两中情况讨论；

第一种情况是：不杀非0的，直接在0类里面从小到大杀，得到一组解；

第二种情况是：如果可以杀死一个非0的，杀死的那个必然是最小的，杀完所有的之后到一些剑，用这些剑先杀0的里面的大的，如果0 类的还剩，

那么把所有的敌人除非0的里面那个最小的外按消耗的能量值再重新排一次序，从小到大再取，一直取到不能取或杀死敌人值达到n，最后得到的就是这种情况的解；

 因为在这时如果你取的是0，那很正常（因为剩下的能量本来就是要来杀敌人的），如果非0那么就相当于用能量替换剑来杀他，而剑自然用来杀后面的大的，所以也要加上；

因为是从小到大进行的，那么结果一定是最大的；

 

最后用这两种情况的解比较即是这题的解了；

ps：今天一直wa，是在于去除非0的里面那个最小的，我以为去掉了，后来用[dut]cube@歪提供那组测试数据才知道其实去掉的并不是最小的，唉，太伤了；

*/

#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int h,cnt;
}num[110000];
bool cmp(node a,node b)
{
    return a.cnt<b.cnt;
}
bool cmp1(node a,node b)
{
    return a.h<b.h;
}
int swd[110000];
int main()
{
    int n,hp,i,j,cass,cas,tag,sum1,sum2,v1,sum,p,Min,yy;
    scanf("%d",&cass);
    for(cas=1;cas<=cass;cas++)
    {
        scanf("%d%d",&n,&hp);
        p=v1=hp;
        for(i=1;i<=n;i++)
            scanf("%d%d",&num[i].h,&num[i].cnt);
        sort(num+1,num+n+1,cmp);
        sum1=sum2=sum=yy=0;
        tag=n;
        for(i=1;i<=n;i++)
        {
            if(num[i].cnt)
            {
                tag=i-1;
                Min=2000000009;
                for(j=i;j<=n;j++)
                {
                    if(num[j].h<Min)
                        Min=num[j].h;
                    sum+=num[j].cnt;
                    swd[yy++]=num[j].h;
                }
                if(Min<=v1)
				{
					sum1=1;
                    v1-=Min;
				}
				else{
					v1=-1;
					sum=0;
				}
                break;
            }
        }
		sort(num+1,num+tag+1,cmp1);
		for(i=1;i<=tag;i++)
        {
            if(hp>=num[i].h)
            {
                sum2++;
                hp-=num[i].h;
            }
            else break;
        }
        if(v1>=0)
        {
			sort(swd,swd+yy);//开始就是掉了这句；
            for(i=1;i<=tag;i++)
				swd[yy++]=num[i].h;
            if(n-sum>0)
                sum1+=sum;
            else sum1=n;
            if(sum1<n)
            {
                sort(swd+1,swd+yy);
                for(i=1;i<yy;i++)
                {
                    if(v1>=swd[i])
                    {
                        sum1++;
                        v1-=swd[i];
						if(sum1==n)
							break;
                    }
                }
            }
        }
        printf("Case %d: ",cas);
		v1=p-v1;
		hp=p-hp;
        if(sum2>sum1)
            printf("%d %d\n",sum2,hp);
        else if(sum1>sum2)
            printf("%d %d\n",sum1,v1);
        else 
            printf("%d %d\n",sum1,(v1<hp)?v1:hp);
    }
    return 0;
}


/*
10

5 100
2 1
1 1
10 0
10 0
10 0

7 999
999 1
999 1
999 1
1 0
1 0
1 0
1 0


*/