Poj 1017: Packets

poj1017.md

Poj 1017: Packets

題目

分析

太扯啦，竟然 WA 了六次…Debug 了快二個小時

在處理 3x3 時，沒注意到不只會產生 2x2 的 space 也會有 1x1 的 space…

這題 Greedy，從大的開始放及可。

AC Code

#include <iostream>
#include <algorithm>
using namespace std;

int data[7];
int remain3x3_2x2[4] = {-1, 5, 3, 1};
int remain3x3_1x1[4] = {-1, 7, 6, 5};

long long solve() {
	long long cnt = 0;
	long long space_for_2x2 = 0;
	long long space_for_1x1 = 0;
	
	// 6
	cnt += data[6];
	
	// 5
	cnt += data[5];
	space_for_1x1 += data[5] * 11;
	
	// 4
	cnt += data[4];
	space_for_2x2 += data[4] * 5;
	
	// 3
	cnt += data[3] / 4;
	if (data[3] % 4 != 0) {
		cnt++;
		space_for_2x2 += remain3x3_2x2[data[3] % 4];
		space_for_1x1 += remain3x3_1x1[data[3] % 4];
	}
	
	// 2
	if (data[2] > space_for_2x2) {
		data[2] -= space_for_2x2;
		space_for_2x2 = 0;
		
		cnt += data[2] / 9;
		if (data[2] % 9 != 0) {
			cnt++;
			space_for_1x1 += 36 - 2 * 2 * (data[2] % 9);
		}
	}
	else {
		space_for_2x2 -= data[2];
	}
	
	// 1
	space_for_1x1 += space_for_2x2 * 4;
	if (data[1] > space_for_1x1) {
		data[1] -= space_for_1x1;
		space_for_1x1 = 0;
		
		cnt += data[1] / 36;
		if (data[1] % 36 != 0) {
			cnt++;
		}
	}
	else {
		space_for_1x1 -= data[1];
	}
	
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	
	while (true) {
		for (int i = 1; i <= 6; i++)
			cin >> data[i];
		
		if (data[1] == 0 && data[2] == 0 && data[3] == 0 &&
			data[4] == 0 && data[5] == 0 && data[6] == 0)
			break;
		
		cout << solve() << endl;
	}
	
	return 0;
}

更簡短的代碼可參考 這 。