首页 > 代码库 > uva311 - Packets(贪心)

uva311 - Packets(贪心)

题目:311 - Packets


题目大意:给出1*1, 2*2,3 *3, 4*4, 5*5, 6*6的箱子的个数,现在有若干个6*6的箱子,问最少用多少个箱子可以将给定的箱子都装进去。


解题思路:对于6 * 6的箱子,每个都要耗费一个箱子。

                 对于5 * 5的箱子, 装完这个后还能再装11个1 * 1.

                 对于 4 * 4的箱子,装完这个后还能装5个2 * 2,然后2 * 2 的不够可以用1 * 1 的补足。

                对于3 * 3 的箱子,情况有3:

                                                          1个3 * 3的箱子, 5 个 2 * 2 的箱子, 7个 1 * 1;

                                                          同上诉格式:2 3 6

                                                                                3 1 5

                 对于需要2的,不足的话就用1的.


代码:

#include <stdio.h>

const int N = 6;
int packets[N];
//补足2*2的空缺
void need () {

	if (packets[1] < 0) {

		packets[0] += packets[1] * 4;
		packets[1] = 0;
	}
}
//判断3*3的特殊的情况
void judge (int a, int b) {
	
	packets[1] -= a;
	packets[0] -= b;
	need();
}

int solve () {

	int sum = packets[5];
	int temp;
	for (int i = N - 2; i >= 1; i--) {

		if (i == 4) {
			
			sum += packets[i];
			packets[0] -= 11 * packets[i];

		} else if (i == 3) {
			
			sum += packets[i];
			packets[1] -= packets[i] * 5;
			need();

		} else if (i == 2) {

			sum += packets[i] / 4;
			packets[i] %= 4;
			if (packets[i] == 3) {

				sum++;
				judge(1,5); 
			} else if (packets[i] == 2) {

				sum++;
				judge(3,6);
			} else if (packets[i] == 1) {

				sum++;
				judge(5,7);
			}
		} else {
			
			temp = packets[1] * 4;
			if (packets[0] > 0)
				temp += packets[0];
			sum += (temp  + 35)/ 36;
		}
	}
	return sum;
}

int main () {

	int count;
	while (1) {

		count = 0;
		for (int i = 0; i < N; i++) {

			scanf ("%d", &packets[i]);
			count += packets[i];
		}
		if (!count)
			break;

		printf ("%d\n", solve());
	}
	return 0;
}