2019牛客多校第六場——D.Move【思維/構造】

連結：https://ac.nowcoder.com/acm/contest/886/D

題目描述

After the struggle of graduating from college, TangTang is about to move from a student apartment to his new home.

TangTang has n items to move, the i-th of which is of volume viv_ivi​. He can pack all these items into at most K boxes of the same volume.

TangTang is so clever that he uses the following strategies for packing items:

- Each time, he would put items into a box by the next strategy, and then he would try to fill another box.

- For each box, he would put an unpacked item of the largest suitable volume into the box repeatedly until there is no such item that can be fitted in the box.

Now, the question is what is the minimum volume of these boxes required to pack all items.

輸入描述:

There are multiple test cases. The first line contains an integer T (1≤T≤201 \leq T \leq 201≤T≤20), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers n, K (1≤n,K≤10001 \leq n, K \leq 10001≤n,K≤1000), representing the number of items and the number of boxes respectively.

The second line contains n integers v1v_1v1​, v2v_2v2​, …\ldots…, vnv_nvn​ (1≤v1,v2,…,vn≤10001 \leq v_1, v_2, \ldots, v_n \leq 10001≤v1​,v2​,…,vn​≤1000), where the i-th integer viv_ivi​ represents the volume of the i-th item.
           

輸出描述:

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case.
           

輸入

1
5 3
1 2 3 4 5
           

輸出

Case #1: 5
           

題意：

給你n個物品，k個箱子，每個物品有自己的體積，對于每一個箱子，剩餘物品按照從大到小的順序放入（能放進去就必須要放，放不了就換小的），問能使用至少k個箱子放下所有n個物品的箱子最小容量是多少。

分析：

确定左界（右界可有可無），然後從小到大check目前是否可行，雖然說最壞情況下複雜度說是有1e6*n*n，但是仔細想不會有這種情況，check的次數大約最多隻有1000次；

左界是max(sum/k,mx)；

這玩意兒沒有二分性！很氣！

原因是：使用較大的箱子裝時可能可以裝進很多個很大的物品，但剩餘的放不進去，于是造成很多的浪費，但如果使用較小的箱子，隻能放進去少數幾個很大的物品，剩餘的空間可以用小物品填充滿，浪費更少，是以可能會出現大箱子不行，小箱子反而可以的情況。

39 10

55 63 83 27 16 23 26 26 15 30 56 39 90 53 38 20 100 67 37 43 42 36 18 4 5 56 1 75 71 29 75 18 93 96 5 87 4 38 17

這組資料正解是169，二分的答案可能是171，就是上面說的情況

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int a[maxn],kk[maxn];
int n,k;
bool check(int mid){
    for (int i=1;i<=k;i++) kk[i]=mid;
    for (int i=1;i<=n;i++){
        int f=0;
        for (int j=1;j<=k;j++)
            if (kk[j]>=a[i]){
                kk[j]-=a[i]; f=1; break;
            }          
        if (!f) return false;
    }
    return true;
}
bool cmp(int p,int q){return p>q;}
int main(){
    int t,x,_=0;scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&k);
        int sum=0,mx=0;
        for (int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum+=a[i]; mx=max(mx,a[i]);
        }
        sort(a+1,a+1+n,cmp);
        int xx;
        if (sum%k==0) xx=sum/k;else xx=sum/k+1;
        xx=max(xx,mx);
        int l=xx,r=sum,mid,ans;
        for (int i=l;i<=r;i++){
            if (check(i)){
                printf("Case #%d: %d\n",++_,i); break;
            }
        }
    }
    return 0;
}