首页 > ACM题库 > HDU-杭电 > HDU 4572-Bottles Arrangement[解题报告]HOJ
2015
09-16

HDU 4572-Bottles Arrangement[解题报告]HOJ

Bottles Arrangement

问题描述 :

  Hunan cuisine is really wonderful! But if you don’t like spicy food, you will feel terrible since it can be hard for you to find any food without hot pepper here. Big Fan is a student from the north who was not fit to the spicy food in Changsha. He became thinner and thinner because eating little food and maintained his life mostly by drinking water. One day, he found that the wine in Hunan is pretty good, such as Jiugui, Liuyang River, Shaoyang Daqu and so on. He got addicted to it and became an alcoholic, leading a depressed life.
  Now N days have passed and he is sobered. He is surprised to find that there are exactly N×M bottles around him. Another amazing fact is that there are N bottles with height 1 and N bottles with height 2 … N bottles with height M.
Now he is interested in playing with these bottles. He wants to arrange all these bottles in a rectangle with M rows and N columns which satisfied:
(1)In any column, there are no bottles with same height;
(2)In any row, the height difference between any two adjacent bottles is no more than 1.
  He defined a strange function Y which equals the maximum value of the total height of any single row. He is addicted in arranging these rubbish bottles to find the minimal Y. You know that he cannot solve it with his pour IQ. You are his friend and can’t endure his decadence any more. So you decide to help him solve this problem and then bring him back to study.

输入:

  There are several test cases. For each case, the input contains one line with two integers M and N (1< M <= 10000, 3 <= N < 2×M, It is guaranteed that N is always odd).
  The input will finish with the end of file.

输出:

  There are several test cases. For each case, the input contains one line with two integers M and N (1< M <= 10000, 3 <= N < 2×M, It is guaranteed that N is always odd).
  The input will finish with the end of file.

样例输入:

3 3
3 5

样例输出:

8
11
Hint
For the first case the solution is: 1 2 3 2 1 1 3 3 2

题目链接: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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/keshuai19940722/article/details/23297797