2019牛客多校D move——乱搞&&思维题

题意

给定 $n$ 个物品，体积分别为 $v_i$，现有 $K$ 的容积一样的箱子，按如下策略装入物品：每次选取尽可能大的装入（较大的不能装入时可以向小的找），依次装入箱子。

分析

首先，不具有严格的单调性，即可能大的箱子不符合但小的符号。与我们的直觉有点不同，是这个策略造成的。

但是基本单调，最优解应该在二分结果附近，于是有了方法一。

方法二：找出答案的上下界，下界 $\left \lceil sum/k \right \rceil$，上界 $ \left \lceil sum/k \right \rceil + maxV$，枚举。

#include<bits/stdc++.h>

using namespace std;

const int maxn =  + ;

int n,k,a[maxn];

multiset<int>st;

bool judge(int mid)

{

    st.clear();int tmpk = k;

    for(int i = ;i < n;i++)  st.insert(a[i]);

    while(!st.empty() && tmpk--)

    {

        int x = mid;

        while(x)

        {

            multiset<int>::iterator it = st.upper_bound(x);  //第一个小于或等于x

            if(it == st.begin()) break;

            it--;

            x -=*it;

            st.erase(it);

        }

    }

    if(!st.empty())  return false;

    return true;

}

int main()

{

    int T, kase=;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d", &n, &k);

        for(int i = ;i < n;i++)

        {

            scanf("%d", &a[i]);

        }

        int l = , r = , ans;

        while(l < r)

        {

            int mid = (l+r)>>;

            if(judge(mid))

            {

                ans = mid;

                r = mid-;

            }

            else l = mid+;

        }

        int res = ans;  //printf("%d\n", ans);

        for(int i = max(, ans-);i <= ans;i++)  //往小一点尝试一下

            if(judge(i))

            {

                res = i;

                break;

            }

        printf("Case #%d: %d\n", ++kase, res);

    }

    return ;

}

参考链接：

1. https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41019801

2. https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41026089