当前位置: 代码迷 >> 综合 >> POJ1017 Packets(贪心)
  详细解决方案

POJ1017 Packets(贪心)

热度:81   发布时间:2024-01-16 13:43:55.0

题意:

有高度相同,底面积为1*1,2*2,3*3……6*6的产品,包裹底面积是6*6的,求最小的包裹数。

要点:

很明显是贪心,思路比较好理清楚,就是优先选大的产品,注意都是向上取整。


15425287 Seasonal 1017 Accepted 164K 16MS C++ 594B 2016-04-22 22:17:47
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int space2[4] = { 0,5,3,1 };//针对3剩余个数用2最多能填充几个int main()
{int a[15];for (;;){bool flag = true;for (int i = 1; i <= 6; i++){scanf("%d", &a[i]);if (a[i] != 0)flag = false;}if (flag)break;int count = a[6] + a[5] + a[4] + (a[3]+3) / 4;//6,5,4都是直接加,3要向上取整int used2 = a[4] * 5 + space2[a[3] % 4];	//2使用的个数,主要用来填充3和4if (a[2] > used2)count += (a[2] - used2 + 8) / 9;		//剩余的2作为新包裹int used1 = count * 36 - a[6] * 36 - a[5] * 25 - a[4] * 16 - a[3] * 9 - a[2] * 4;//1无所谓,可以填充所有的包裹剩下的空间if (a[1] > used1)count += (a[1] - used1 + 35) / 36;//如果1填充完所有的还有剩,就作为新包裹printf("%d\n", count);}return 0;
}


  相关解决方案