鏈接：
http://poj.grids.cn/practice/1017
說實話這就是個簡單的裝箱子問題,很容易想清楚裝箱子的過程,而且這個過程是滿足貪心算法的,
所以只需要用代碼模擬整個裝箱子的過程即可,但是這樣真的就足夠了嗎？？？
我剛開始就是用代碼模擬這個手動過程了,雖然AC了,但是代碼有150行左右,邏輯也顯得過于復雜了,
得不償失。。。整個過程是6*6的一個占一個箱子,5*5的也必須一個占一個箱子,但是需要補11個1*1的,
4*4的也是一個占一個箱子,但是需要補5個2*2的,如果2*2的不足夠,則用1*1的代替,
3*3的4個占一個箱子,但是會有余數,可能余下1,2,3個3*3的箱子,這個時候必須非情況考慮,
1個3*3的需要和5個2*2的,7個1*1的組合,2個3*3的需要和3個2*2的,6個1*1的組合,
3個3*3的需要和1個2*2的,5個1*1的組合,最后考慮9個2*2的裝一個箱子,多余的2*2用1*1的去填充盡量擠滿一個箱子,
最后36個1*1的裝一個箱子,余下的1*1的也必須占一個箱子。。。
這個過程說出來已經非常復雜了,更何況用代碼寫,我費了九牛二虎之力才寫出來,WA了一次才AC了...
代碼:
#include <stdio.h>
int main()
{
int one, two, three, four, five, six;
int num = 0;
while (scanf("%d%d%d%d%d%d", &one, &two, &three, &four, &five, &six) == 6)
{
if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
{
break;
}
num = six;
num += five;
if (one > five * 11)
{
one -= five * 11;
}
else
{
one = 0;
}
num += four;
if (two > four * 5)
{
two -= four * 5;
}
else
{
if (one > four * 5 * 4 - two * 4)
{
one -= four * 5 * 4 - two * 4;
}
else
{
one = 0;
}
two = 0;
}
num += three / 4;
three = three % 4;
if (three == 1)
{
if (two > 5)
{
two -= 5;
if (one > 7)
{
one -= 7;
}
else
{
one = 0;
}
}
else
{
if (one > 27 - two * 4)
{
one -= 27 - two * 4;
}
else
{
one = 0;
}
two = 0;
}
++num;
}
if (three == 2)
{
if (two > 3)
{
two -= 3;
if (one > 6)
{
one -= 6;
}
else
{
one = 0;
}
}
else
{
if (one > 18 - two * 4)
{
one -= 18 - two * 4;
}
else
{
one = 0;
}
two = 0;
}
++num;
}
if (three == 3)
{
if (two > 1)
{
two -= 1;
if (one > 5)
{
one -= 5;
}
else
{
one = 0;
}
}
else
{
if (one > 9 - two * 4)
{
one -= 9 - two * 4;
}
else
{
one = 0;
}
two = 0;
}
++num;
}
num += two / 9;
two = two % 9;
if (two)
{
if (one > 36 - two * 4)
{
one -= 36 - two * 4;
}
else
{
one = 0;
}
++num;
}
num += one / 36;
if (one % 36)
{
++num;
}
printf("%d\n", num);
}
return 0;
}
這樣的寫法顯然不好吧。。。首先,余下1,2,3個3*3時候需要填幾個2*2的可以存儲在數組里面,這樣就可以不用寫重復代碼了,
如果再從整體考慮余下多少個格子,就不用用貪心算法模擬裝箱子的過程了。。。
代碼如下:
#include <stdio.h>
int main()
{
int one, two, three, four, five, six;
int num = 0;
int twoPlace[4] = {0, 5, 3, 1};
int remTwo, remOne;
while (scanf("%d%d%d%d%d%d", &one, &two, &three, &four, &five, &six) == 6)
{
if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
{
break;
}
num = six + five + four + (three + 3) / 4;
remTwo = four * 5 + twoPlace[three % 4];
if (two > remTwo)
{
num += (two - remTwo + 8) / 9;
}
remOne = 36 * num - 36 * six - 25 * five - 16 * four - 9 * three - 4 * two;
if (one > remOne)
{
num += (one - remOne + 35) / 36;
}
printf("%d\n", num);
}
return 0;
}