nowcoder多校6-Move

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

发表留言

人生在世,错别字在所难免,无需纠正。