題意：給定一些矩形，面積分別是 \(1\times 1,2\times 2,3\times 3,4\times 4,5\times 5,6\times 6\)，您現在知道了這些矩形的個數 \(a,b,c,d,e,f\)，需要將這些矩形一個不落的裝到一種面積為 \(6\times 6\)的大矩形里面，問如何使大矩形的數量最少（輸入包含多組資料，以全部都是 0 結尾），
樣例輸入：
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
樣例輸出：
2
1
分組考慮，首先，我們知道對于 \(6\times 6,5\times 5,4\times 4\)的矩形一個大矩形中只能占一個，如圖
于是設每次答案為 \(\text{ans}\)，則答案最少為 \(\text{ans+d+e+f}\)，
順著剛剛的思路，單獨考慮對于 \(3\times 3\)的情況，不難發現，一個大矩形最多可以接納 4 個 \(3\times 3\) 的矩形，換而言之，4 個這樣的小矩形占用一個大矩形，考慮到余數，則答案需再加上 \((c+3)/4\)，（補 3 除 4，在本題中這是一個很重要的思路），
于是當前答案有：int ans=(d+e+f+(c+3)/4);
接著，考慮面積為 \(2\times 2\) 的矩形的情況，注意到被藍色和紅色區域“占領”的面積都無法接納 \(2\times 2\)的矩形，那么考慮已經裝入 \(4\times 4\) 和 \(3\times 3\) 的， \(4\times 4\)的比較好想，顯而易見的最多只能填入 5 個，對于 \(3\times 3\) 的矩形，分別考慮裝入一個 \(3\times 3\)，兩個 \(3\times 3\) 和三個 \(3\times 3\) 的情況，思考可以發現對應的答案分別為 \(5,3,1\) ，由于 \(3\times 3\) 的數量不確定，可以開一個陣列記錄，即 int mod[4]={0,5,3,1};，然后設變數 \(y\) 為當前答案下最多能裝入的 \(2\times 2\) 的數量，把這個值與輸入的 \(2\times 2\) 的數量作比較，若比輸入的數量少，則說明剩下的此型別的矩形只有單獨放，根據“補 3 除 4”的原則易得還需加上的新矩形為 (b-y+8)/9 個，
最后，考慮 \(1\times 1\) 的矩形，這種矩形很特殊，我們分析發現它的一個性質——它不涉及填入后留空位的問題，啥意思呢？也就是說，我們采用“見縫插針”的方式，即，有多少空就都填滿，但是，如果還像上面那樣加加除除的話太麻煩了，于是，考慮如下的演算法：
首先考慮，對于當前答案的所有面積，若都填一，則能填多少；然后減去其他占用的面積，最后按照如上的方式比較是否需要新增，
以上，就是本題的貪心策略，自證不難
#include <iostream>
#include <cstdio>
using namespace std;
int mod[4]={0,5,3,1};
int main()
{
int a,b,c,d,e,f;
while(1)
{
cin>>a>>b>>c>>d>>e>>f;
if(!a&&!b&&!c&&!d&&!e&&!f)break;
int ans=(d+e+f+(c+3)/4);
int y=5*d+mod[c%4];
if(b>y)ans+=(b-y+8)/9;
int x=36*ans-(36*f+25*e+16*d+9*c+4*b);
if(a>x)ans+=(a-x+35)/36;
cout<<ans<<endl;
}
return 0;
}
/*
data:
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63277.html
標籤：C++
上一篇：【做題筆記】P1042 乒乓球
下一篇：【學習筆記】[圖論]樹的直徑