球球大作战

二分+贪心
球球大作战
题意：有n个球，每次可合并任意相邻两个球为一个球，合并之后的球的体积为这两相邻球体积之和。现在有m次合并，经过这m次合并之后，希望剩下球中体积的最小值能够最大(采用最佳合并策略)。
分析：假如我已经知道答案即合并之后剩下球中体积的最小值的最大值为a，然后我应该怎么判断如何合并能够得到这种情况的结果呢？很容易可以想到
要从第一个球开始合并直到结果>=a时停止合并，继续重复这个合并过程 **剩下的就是找出来这个a，所以要使用二分查找。**若这个要测试的值为temp,算出来一个到达temp这个结果的总次数为m，即a=temp; 总次数大于m:正确答案的合并次数比较少，则a<temp;反之总次数小于m，则a>temp. (a越小，合并的次数越少，因为很容易几个数加起来到达a，到达一次少合并一次）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int a[N],n,m;
bool solve(ll fin,int n,int m)//fin为每一次要查找的值，要加上n,m....
{
    ll tmp=0;
    for(int i=1;i<=n;i++)
    {
        tmp+=a[i];
        while(tmp<fin&&i<=n)//每一次合并的过程
        {
            i++;
            tmp+=a[i];//tmp用来记录每一次小合并的和
            m--;//m为可用的次数，减1
        }
        if(tmp<fin)//这是不是有点问题！！好像真的有问题
            m=-1;              
        if(m<0)//该查找的值用的次数大于m
        return false;
        if(n-i<=m)//假若有剩下的个数小于合并的次数，明显该值需要的次数小于m，不需要往下继续合并了
            return true;
        tmp=0;//合并一次便归零
    }
    if(m>=0)
        return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll sum=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        ll high=sum,low=1,mid,fin;//high的起始值为所有都合并的情况
        while(high>=low)
        {
            mid=(high+low)/2;
        if(solve(mid,n,m))//返回true代表这个值用的次数较少，这个值比真实值要小，继续往上查找
            low=mid+1,fin=mid;
        else
            high=mid-1;
        }
        printf("%lld\n",fin);
    }
    return 0;
}

本来我以为是dp，但跟不知道怎么从前面的状态m-1次推，最小值里面的最大值乱七八糟的，真实也推不了吧，对我来讲肯定是推不了…