首页 > ACM题库 > HDU-杭电 > HDU 4415-Assassin’s Creed-贪心-[解题报告]HOJ
2015
07-16

HDU 4415-Assassin’s Creed-贪心-[解题报告]HOJ

Assassin’s Creed

问题描述 :

Ezio Auditore is a great master as an assassin. Now he has prowled in the enemies’ base successfully. He finds that the only weapon he can use is his cuff sword and the sword has durability m. There are n enemies he wants to kill and killing each enemy needs Ai durability. Every time Ezio kills an enemy he can use the enemy’s sword to kill any other Bi enemies without wasting his cuff sword’s durability. Then the enemy’s sword will break. As a master, Ezio always want to do things perfectly. He decides to kill as many enemies as he can using the minimum durability cost.

输入:

The first line contains an integer T, the number of test cases.
For each test case:
The first line contains two integers, above mentioned n and m (1<=n<=10^5, 1<=m<=10^9).
Next n lines, each line contains two integers Ai, Bi. (0<=Ai<=10^9, 0<=Bi<=10).

输出:

The first line contains an integer T, the number of test cases.
For each test case:
The first line contains two integers, above mentioned n and m (1<=n<=10^5, 1<=m<=10^9).
Next n lines, each line contains two integers Ai, Bi. (0<=Ai<=10^9, 0<=Bi<=10).

样例输入:

2
3 5
4 1
5 1
7 7
2 1
2 2
4 0

样例输出:

Case 1: 3 4
Case 2: 0 0

/*
分析:
    贪心。
    1、所有人都没有菜刀、无法砍别人。对于这种情况,直接根据cost排序,
来尽量多的杀人,得到第一组ans;
    2、存在有菜刀的人:
    如果猪角的武器的耐久、不足以使他杀死“有菜刀、且cost最小”的人,那
么返回“1、”,否则、砍死这个人、进入下面的步骤:
(1)所有的人的菜刀可以杀死的人的总和sum+1>=n(因为至少一个人必须是
猪角用自己的武器杀死的),那么最多可以杀n个人;
    (2)上述sum+1<n,那么去除猪角已经砍死的那个人,然后根据cost排序,直
接干掉cost最大的sum个人,然后用猪角自己的武器、从还活着的人中、从cost
从小到大、尽量多杀人;
    (1)和(2)的最优为第二组ans;
    
    比较第一、二组ans,最优既为所求。
    至于2.(2),为什么可以直接先干掉cost最大的sum个人呢?根据菜刀可杀人
总数守恒、我们总可以把所有的菜刀都完美利用起来,可以拿张纸画下,所以、
如何完美的利用菜刀是解决此题的关键。。。

                                                                 2013-06-27
*/

#include"iostream"
#include"cstdio"
#include"queue"
#include"cstring"
#include"algorithm"
using namespace std;
const int N=100005;

int n,m,cnt1,cnt2;
int ans1,ans2,ret1,ret2,zz[N];
struct node{
	int cost,val;
}E[N];
int cmp(node n1,node n2){
	return n1.cost<n2.cost;
}

void solve1()
{
	int i;
	ans1=0;
	ret1=m;
	for(i=0;i<n;i++)
	{
		if(E[i].val)	continue;
		if(ret1>=E[i].cost)	{ans1++;ret1-=E[i].cost;}
		else	break;
	}
}
void solve2()
{
	int i;
	ans2=0;
	ret2=m;
	for(i=0;i<n;i++)	if(E[i].val)	break;
	if(i>=n)			return ;
	if(ret2<E[i].cost)	return ;

	int flag=i;
	int sum=0;
	for(i=0;i<n;i++)	sum+=E[i].val;
	if(sum+1>=n)	{ans2=n;ret2=m-E[flag].cost;return ;}

	ans2=sum+1;
	ret2-=E[flag].cost;
	memset(zz,0,sizeof(zz));
	zz[flag]=1;
	i=n-1;
	while(sum>0)
	{
		if(!zz[i])	{zz[i]=1;sum--;}
		i--;
	}
	for(i=0;i<n;i++)
	{
		if(zz[i])	continue;
		if(ret2<E[i].cost)	break;
		ans2++;
		ret2-=E[i].cost;
	}
}
int main()
{
	int T,Case;
	int i;
	cin>>T;
	for(Case=1;Case<=T;Case++)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)	scanf("%d%d",&E[i].cost,&E[i].val);

		sort(E,E+n,cmp);
		solve1();
		solve2();
		if(ans1>ans2 || (ans1==ans2 && ret1>ret2))
			printf("Case %d: %d %d\n",Case,ans1,m-ret1);
		else	printf("Case %d: %d %d\n",Case,ans2,m-ret2);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/9191073


  1. 有预感这下无聊图会变成老阿訇讲经堂,阿訇们从珍藏经书中截出很正常的片段,然后讲一波经,既是原创,也受群众欢迎,美滋滋。

  2. 有预感这下无聊图会变成老阿訇讲经堂,阿訇们从珍藏经书中截出很正常的片段,然后讲一波经,既是原创,也受群众欢迎,美滋滋。

  3. 有预感这下无聊图会变成老阿訇讲经堂,阿訇们从珍藏经书中截出很正常的片段,然后讲一波经,既是原创,也受群众欢迎,美滋滋。

  4. 有预感这下无聊图会变成老阿訇讲经堂,阿訇们从珍藏经书中截出很正常的片段,然后讲一波经,既是原创,也受群众欢迎,美滋滋。

  5. 有预感这下无聊图会变成老阿訇讲经堂,阿訇们从珍藏经书中截出很正常的片段,然后讲一波经,既是原创,也受群众欢迎,美滋滋。