2019牛客暑期多校訓練營（第六場）D Move

題目連接配接：https://ac.nowcoder.com/acm/contest/886/D

題意：有n個物品，每個物品的容積為a[i],現在給k個箱子，求滿足将所有物品裝到k個箱子裡的最小的箱子的容積。

解析：首先求出可能滿足條件的下界ceil（sum/k）, 然後 ，從下屆開始枚舉，對于每個答案check一下就可以了。

#include<bits/stdc++.h>
using namespace std;
const int  Maxn = 1500;
int n , k , ans , sum , a[Maxn];
int vis[Maxn];
bool check(int x){
    int t = 0;
    memset(vis ,0 ,sizeof(vis));
    for(int i = 1;i <= k;i++){
        int cnt = x;
        for(int j = n;j >= 1;j--){
            if(!vis[j] && cnt - a[j] >= 0){
                cnt -= a[j];
                vis[j] = 1;
                t++;
            }
        }
    }
    return t == n;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int num = 1;num <= T;num++){
        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);
        ans = (sum + k -1) / k ;
        //cout <<sum <<" "<< ans <<endl;
        for(int i = ans ;;i++){
            if(check(i)){
                ans = i;
                break;
            }
        }
        printf("Case #%d: %d\n",num , ans);
    }
}