hdu 4572 Bottles Arrangement（构造）

题目链接：hdu 4572 Bottles Arrangement

题目大意：给定m和n，表示有m种高度的瓶子，每种瓶子n个，现在将n*m个瓶子排列成一个m行n列的矩阵，要求：1，每一列没有相同高度的瓶子；2，每一行相邻的两个瓶子的高度差的绝对值不大于1。然后所有满足条件的矩阵有一个值，即为每一行所有元素之和的最大值。要求构造出一个矩阵，使得该值最小。

解题思路：我是从最大的瓶子开始考虑的，除非放在最左或是最右，否则一个最大号的瓶子要消耗两个第二大的瓶子（条件1），以7为例，

7 6 ...

6 7 7 6...

4 5 6 7 7 6

2 3 4 5 6 7

这样的方法是最优的，而且最大值肯定为中间那行。

#include <stdio.h>
#include <string.h>

int main () {
	int m, n;
	while (scanf("%d%d", &m, &n) == 2) {
		int t = m - n/2 + 1;
		int s = (t + m) * (n/2);
		printf("%d\n", s + t - 1);
	}
	return 0;
}