[UVA][greedy] 12520 - Square Garden
Square Garden
| Square Garden |
The farmer Rick has a square garden of side L meters long, divided in a grid with L2 square modules, each one of side 1 meter long. Rick wants to cultivate N modules of the garden and he knows that the production will be better if the cultivated area receives more water. He uses drip irrigation technology, which is done by means of hoses installed along the perimeter of the cultivated area.
It should be clear that there are different ways to choose the N modules that should be
cultivated. The following figure shows two ways to cultivate N = 8 modules in a square garden
with side L = 3. The left diagram shows a cultivated surface with a perimeter of length 16;
the right one depicts another possibility, with perimeter 12.
Rick wants to maximize the perimeter of the selected area in order to optimize the
production. Then you have been hired to help him determining the largest perimeter that an area of
N modules of the garden may attain.
Input
There are several cases to consider. Each case is described with a line with two integer
numbers L and N separated by one blank, indicating the length of the garden's side and the
number of modules that must be cultivated, respectively (
1 
L 106,
0 N L2). Input ends with a line with two `0' values.
Output
For each case, output a line with the maximum perimeter that can be achieved.
Sample Input
1 0 1 1 2 3 3 8 0 0
Sample Output
0 4 8 16
題目描述：
在一個 LxL 的方形土地中，任意占據 N 格，使得周長最大。
求周長最大為何？
題目解法：
greedy 策略，先找到最大的可能，黑白染色類似國際象棋的方式。
然後對於 L 是奇數填法會要考慮兩種情況。
L 是奇數
1) 情況 1，一般黑白染色(最左上角是黑色)
依序先填邊界上的空白處，因為這些點每增一格會少 2 周長。
逼不得已只好往裡面填入，每增一格會少 4 周長。
2) 情況 2，顛倒黑白色上(最左上角是白色)
處理情況類似，不過最優先處理填入到棋盤四個角落。因為這些不會減少周長。
L 是偶數
先處理填入兩個角落，其餘處理情況類似。
#include <stdio.h>
int main() {
long long L, N;
while(scanf("%lld %lld", &L, &N) == 2 && L) {
long long g = L*L/2 + L%2;
if(N <= g) {
printf("%lld\n", N*4);
continue;
}
if(L&1) {
long long tN = N, ans1 = g*4, ans2 = 4*(g-1);
N -= g;
if(N >= 4*(L/2)) {
ans1 -= 2*4*(L/2);
N -= 4*(L/2);
ans1 -= N*4;
} else {
ans1 -= N*2;
N = 0;
}
tN -= g-1;
if(tN > 4) tN -= 4;
else tN = 0;
if(tN >= 4*(L/2-1)) {
ans2 -= 2*4*(L/2-1);
tN -= 4*(L/2-1);
ans2 -= tN*4;
} else {
ans2 -= tN*2;
tN = 0;
}
printf("%lld\n", ans1 > ans2 ? ans1 : ans2);
} else {
long long ans = g*4;
N -= g;
if(N > 2) N -= 2;
else N = 0;
if(N >= 4*(L/2-1)) {
ans -= 2*4*(L/2-1);
N -= 4*(L/2-1);
} else {
ans -= N*2;
N = 0;
}
ans -= N*4;
printf("%lld\n", ans);
}
}
return 0;
}