题意：按照有n个物体按照题意的要求（也就是从大到小尽量放尽量少的盒子），然后最多放到k个容量相等的盒子里
问你盒子的容量最小是多少
题解：首先肯定都想到了二分，但是二分基本上没有过的，这时候就应该考虑到函数不单调，这个题的下是sum/k
所以直接从下界网上枚举就可以
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define ms(s) memset(s, 0, sizeof(s)) const int INF = 0x3f3f3f3f; const double eps = 1e-8; const int maxn = 2000+5; const int mod = 998244353; int n,k; int c[maxn],a[maxn]; int check(int x){ int coun=0; ms(c); for(int i=n;i>=1;i--){ int flag=0; for(int j=0;j<coun;j++){ if(c[j]+a[i]<=x){ c[j]+=a[i]; flag=1; break; } } if(!flag){ c[coun++]=a[i]; } if(coun>k)return 0; } return 1; } int main() { int t,kase=0; scanf("%d",&t); while(t--){ int 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+n+1); int ans=sum/k; while(!check(ans))ans++; printf("Case #%d: %d\n",++kase,ans); } return 0; }
