计蒜客——分组

题目描述： 对于一串数 $num$ ，比如 $num=[1,3,4,7,1,4,3,8]$ ，可以将数组中连续若干个数合并为一组 gig_igi​ 。将这串数组分成至多 $k$ 组，当 $k=4$ 的时候，每组数的乘积的最大值 max(gi)\max(g_i)max(gi​) 最小是多少？

输入格式

输入第一行一个整数 n,k(1≤n,k≤10000,0≤⌈nk⌉≤10)n, k (1 \le n, k \le 10000, 0 \le \lceil\frac{n}{k}\rceil \le 10)n,k(1≤n,k≤10000,0≤⌈kn​⌉≤10)。

接下来一行输入 $n$ 个空格隔开的整数 li(1≤li≤9)l_i(1 \le l_i \le 9)li​(1≤li​≤9)，表示数组中数的值。

输出格式

输出每组数的乘积的最大值最小是多少。

样例输入1 4 3

8 4 3 7 样例输出1 12

样例输入2 8 3

2 3 4 2 4 2 4 8 样例输出2 32

题目分析：分析：当k越大时，即分组越多时，max(gi)会越来越小(有时不变，但一定不会增大)。故k和max(gi)呈现负相关的关系。 方法分析：二分搜索+贪心 #include <iostream> #include <cmath> #define maxn 100000 using namespace std; long long s[maxn],n; bool guess(long long mid,long long s[],long long k) {//最大值为mid时，k最小 long long sum=1; for(int i=0;i<n;i++){//一共有k个箱子，箱子的最大容量为mid if(sum*s[i]>mid){//箱子装不下了，需要换下一个箱子来装 --k; sum=s[i];//(等价于sum=0,sum+=s[i]) if(s[i]>mid){//箱子装不下s[i]这件物品 return false; } }else{ sum*=s[i]; } } return k>=1;//最后需要留下一个箱子装sum里的物品 } int main() { long long k; cin>>n>>k; for(int i=0;i<n;i++){ cin>>s[i]; } long long left=1; long long ans; long long right=10e10+1;//n/k<=10,查找的上界限最大只会是10e10。 while(left<right){ long long mid=(left+right)/2; if(guess(mid,s,k)){//猜测mid是符合要求的ans ans=mid; right=mid;//如果k和max(gi)是正相关的关系，则left=mid;这里是负相关的关系，所以是right=mid; }else{ left=mid+1;//同上 } } cout<<(ans)<<endl; return 0; }