当前位置：CGaZn的博客 > OI > 正文

[POJ1017]Packets[贪心]

2019-08-21 分类：OI / 题解阅读(57) 评论(0)

题意: 要用尽量少的6*6的箱子放入一些1*1~6*6的物品, 设他们分别有$latex a_i$个.

首先答案至少要$latex a_6+a_5+a_4$这么多, 因为他们是不能多个并存的. 然后对于5*5和4*4的物品我们就可以贪心地在空隙中插入物品. 对于放了5*5的箱子每个可以插11个1*1. 对于放了4*4的箱子每个可以放5个3*3和7个1*1, 如果放不满就尽可能放1*1. 最后考虑3*3的, 尽量每4个放满一个箱子, 然后讨论剩余1, 2, 3个4*4时能插入多少个1*1和2*2. 最后剩下的1*1和2*2随便放.

由于放每个物品时都尽可能利用所有的空间, 并且都排除了不可行解(不可能放多个的情况), 可以出全局最优. 思路简单, 细节多, 情况要考虑周全.

展开代码

#include<cstdio>
#include<algorithm>
#define re register
#define in inline
#define int long long
using namespace std;
in int read()
{
	int s(0),b(0);char ch;
	do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	if(b)return -s;return s;
}
int a[7];
signed main()
{
	while(1)
	{
		int ans=0,bb=0;
		for(re int i=1;i<=6;++i) a[i]=read(),bb|=a[i];
		if(!bb) break;
		ans=a[6]+a[5]+a[4];
		a[1]=a[1]-a[5]*11;
		if(a[1]<0) a[1]=0;
		a[2]=a[2]-a[4]*5;
		if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
		if(a[1]<0) a[1]=0;
		if(a[2]<0) a[2]=0;
		ans=ans+a[3]/4;
		a[3]%=4;
		if(a[3]) ++ans;
		if(a[3]==1){
			a[2]=a[2]-5;
			if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
			a[1]-=7;
			if(a[1]<0) a[1]=0;
		}
		if(a[3]==2){
			a[2]=a[2]-3;
			if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
			a[1]-=6;
			if(a[1]<0) a[1]=0;
		}
		if(a[3]==3){
			a[2]=a[2]-1;
			if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
			a[1]-=5;
			if(a[1]<0) a[1]=0;
		}
		if(a[2]<0) a[2]=0;
		if(a[2])
		{
			ans=ans+a[2]/9;
			a[2]%=9;
			if(a[2]) ++ans;
			a[1]=a[1]-(36-a[2]*4);
			if(a[1]<0) a[1]=0;
		}
		if(a[1])
		{
			ans=ans+a[1]/36;
			a[1]%=36;
			if(a[1]) ++ans;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

赞(0)

标签：贪心

相关推荐

评论抢沙发