题目链接:nowcoder多校6-Move
题意:
n个物品,每个物品的体积为vi,然后有k个箱子,每个箱子的容积一样,只有当一个箱子装不下的时候才能把东西放入下一个箱子中,问箱子的最小容积。
题解:
这道题不具有单调性!!!不能二分!!!
显然答案有一个下界为ceil(sum/k),显然也有一个上界,所以只需要枚举答案进行检验即可。
参考代码:
#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 5e4 + 5;
int T;
int n, k;
int a[1003], sum, now[1003];
bool check(int res)
{
memset(now, 0, sizeof(now));
for (int i = n; i >= 1; i--)
{
bool flag = 1;
for (int j = 1; j <= k; j++)
if (now[j] + a[i] <= res)
{
now[j] += a[i];
flag = 0;
break;
}
if (flag)
return 0;
}
return 1;
}
int main()
{
scanf("%d", &T);
int icase = 0;
while (T--)
{
sum = 0;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), sum += a[i];
sort(a + 1, a + 1 + n, [](int x, int y) { return x < y; });
int minn = sum / k;
if (sum % k)
minn++;
int ans;
for (int i = 0;; i++)
{
ans = minn + i;
if (check(ans))
break;
}
printf("Case #%d: %d\n", ++icase, ans);
}
return 0;
}