poj1017 Packets(贪心)
思路来源
https://blog.csdn.net/liuke19950717/article/details/50950419
题意
给你若干1*1,2*2,3*3,4*4,5*5,6*6的箱子,
你有一堆6*6的容器,问需要多少个容器才能放下上述箱子。
题解
思路肯定是,
6*6一个容器只能放一个,5*5能填1*1就填,
4*4先填2*2,再填1*1;
3*3先优先4个的放,再填2*2,再填1*1
2*2先优先18个的放,
剩下的2*2和1*1,看占地面积是0,还是0-36之间,还是36-72之间。
代码实现①
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
const int INF=0x3f3f3f3f;
const int maxn=10005;
const int mod=1e9+7;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
ll a,b,c,d,e,f;
int main()
{
while(~scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&f)&&a+b+c+d+e+f)
{
ll ans=0,t;
ans+=f;
ans+=e;a-=min(11*e,a);
ans+=d;t=min(5*d,b);b-=t;a-=min(a,(ll)20*d-4*t);
ans+=c/4,c%=4;
if(c==3)
{
t=min(b,(ll)1);
b-=t;
a-=min(a,(ll)9-4*t);
ans++;
}
else if(c==2)
{
t=min(b,(ll)3);
b-=t;
a-=min(a,(ll)18-4*t);
ans++;
}
else if(c==1)
{
t=min(b,(ll)5);
b-=t;
a-=min(a,(ll)27-4*t);
ans++;
}
ans+=b/9,b%=9;
if(4*b+a)ans+=(4*b+a)%36?(4*b+a)/36+1:(4*b+a)/36;
printf("%lld\n",ans);
}
return 0;
}
代码实现②
感觉自己的实现太暴力了,就是暴力枚举,上网找了一下答案。
答案的确写的简洁,先优先把能填的2*2填了,记一下填的数量。
再考虑剩下的位置用1*1填,最后2*2和1*1二者凑箱子。
tab数组的操作,也值得学习。
//x[1]-x[6]分别对应1*1...6*6的箱子
typedef long long ll;
ll tab[]={0,5,3,1};//tab[i]表示放i个3*3的,还能放多少2*2的
ll solve(ll x[])
{
ll num3=ceil(x[3]/4.0);//3*3的必须使用的盒子数量
ll ans=x[6]+x[5]+x[4]+num3;//不包括1*1和2*2 时必须使用的盒子的数量
ll num2=5*x[4]+tab[x[3]%4];//统计能放2*2的个数
num2=min(num2,x[2]); //计算能使用的2*2的方块最大数量
x[2]-=num2;//2*2的方格使用掉
ll rest=36*ans-x[6]*36-x[5]*25-x[4]*16-x[3]*9-num2*4;//剩余位置
rest=min(rest,x[1]);//能使用1*1的最大数量
x[1]-=rest;//使用1*1的方块
rest=x[2]*4+x[1];//看是否有剩余,有的话,单独找个大箱子
return ans+ceil(rest/36.0);
}