2019牛客暑期多校训练营（第六场）D-Move 【暴力枚举】

2019牛客暑期多校训练营（第六场）D-Move

题目：https://ac.nowcoder.com/acm/contest/886/D

大致题意：

给你两个正整数n， k，范围0~1000，表示有n件行李，用k个相同体积的箱子去装他们，接下来给出n个正整数vi 表示每件行李的体积。把行李放入箱子的规则是：

每次都挑选最大行李放入箱子中，当无法放入的时候才拿下一个箱子继续放入，直到把所有行李都装入k个箱子中

最后问你每个箱子能取的最小体积是多少。

参考资料：https://blog.csdn.net/anthony1314/article/details/98472917

思路：

这题数量很小，所以可以用暴力枚举解题。当然我们还是要简单分析一下箱子体积取值的上下界来加快暴力，以免TLE。在分析的时候我们可以暂时不管箱子的数量。因此（设所有行李体积总和为sum）：
下界：sum / k
上界：sum （一个箱子装完全部东西）
接下来暴力尝试每个答案即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn = 1005;
int n, k;
int goods[maxn];
bool used[maxn];
//goods[]表示行李的数据，并且排序
//used[]表示在枚举的时候，对应的行李是否被放入箱子
bool check(int volume) {
	//初始化所有行李未放入箱子
	for(int i = 0; i < n; i++)
		used[i] = false;
	//按照规则尝试把所有行李放入k个箱子中
	for(int i = 1; i <= k; i++) {
		int temp = 0;
		for(int j = n-1; j >= 0; j--) {
			if(!used[j] && temp + goods[j] <= volume) {
				used[j] = true;
				temp += goods[j];
			}
		}
	}
	//最后检查是否所有行李都放入箱子中
	//若有行李没有被放入箱子，则答案错误
	//反之答案正确
	for(int i = 0; i < n; i++)
		if(used[i] == false)
			return false;
	return true;
}

int main() {
	int T;
	while(~scanf("%d",&T)) {
		for(int cas = 1; cas <= T; cas++) {
			scanf("%d %d",&n, &k);
			int sum = 0;
			for(int i = 0; i < n; i++) {
				scanf("%d",&goods[i]);
				sum += goods[i];
			}
			//排序让行李从小到大排放
			sort(goods, goods+n);
			int ans = 0;
			for(int i = sum / k; i <= sum; i++) {
				if(check(i) == true) {
					ans = i;
					break;
				}
			}
			printf("Case #%d: %d\n", cas, ans);
		}
	}
	return 0;
}