2013
11-10

# Flow Layout

A flow layout manager takes rectangular objects and places them in a rectangular window from left to right. If there isn’t enough room in one row for an object, it is placed completely below all the objects in the first row at the left edge, where the order continues from left to right again. Given a set of rectangular dimensions and a maximum window width, you are to write a program that computes the dimensions of the final window after all the rectangles have been placed in it.

For example, given a window that can be at most 35 units wide, and three rectangles with dimensions 10 x 5, 20 x 12, and 8 x 13, the flow layout manager would create a window that looked like the figures below after each rectangle was added.

The final dimensions of the resulting window are 30 x 25, since the width of the first row is 10+20 = 30 and the combined height of the first and second rows is 12+13 = 25.

The input consists of one or more sets of data, followed by a final line containing only the value 0. Each data set starts with a line containing an integer, m, 1 <= m <= 80, which is the maximum width of the resulting window. This is followed by at least one and at most 15 lines, each containing the dimensions of one rectangle, width first, then height. The end of the list of rectangles is signaled by the pair -1 -1, which is not counted as the dimensions of an actual rectangle. Each rectangle is between 1 and 80 units wide (inclusive) and between 1 and 100 units high (inclusive).

For each input set print the width of the resulting window, followed by a space, then the lowercase letter “x”, followed by a space, then the height of the resulting window.

35
10 5
20 12
8 13
-1 -1
25
10 5
20 13
3 12
-1 -1
15
5 17
5 17
5 17
7 9
7 20
2 10
-1 -1
0


30 x 25
23 x 18
15 x 47

//* @author:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int max_width;
while((max_width=cin.nextInt())!=0){
int final_width=0;
int final_height=0;
int remain=max_width;
int cur_height=0;
int r_width=cin.nextInt();
int r_height=cin.nextInt();
while(r_width!=-1){
if(r_width<=remain){
remain-=r_width;
if(final_width< max_width-remain)
final_width=max_width-remain;
if(cur_height< r_height)
cur_height=r_height;
}
else{
final_height+=cur_height;
cur_height=r_height;
remain=max_width-r_width;
}
r_width=cin.nextInt();
r_height=cin.nextInt();
}
if(final_width< max_width-remain)
final_width=max_width-remain;
final_height+=cur_height;
System.out.println(final_width+" x "+final_height);
}
}
}

1. #include <cstdio>

int main() {
int n, u, d;
while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
if(n<=u) { puts("1"); continue; }
n-=u; u-=d; n+=u-1; n/=u;
n<<=1, ++n;
printf("%dn",n);
}
return 0;
}

2. 样例输出和程序输出不吻合，修改一下样例输出吧。我用的是VC编译器，会提示我的i和j变量重复定义

3. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

4. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮