一道编程题，请讲一下思路就好。

Question

2013届院赛开始了，有许多东西要从购物的卡车上搬到机房。因为车门大小有限，所以每个人抱的物品的序号是连续的。有m个人被叫来搬东西，他们很不高兴，不高兴的程度就是他所搬物品的总重量。现在有n件物品，有m个人，若要使得最大的不高兴度最小，问此时最不高兴的人搬着多重的物品。
我看到过的写法是用二分法，但是我不是很懂，能不能解释下。
#include<stdio.h>
int a[1000001];
main(){
int n,m,i,l,r,mid,sum=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
r=sum;
l=0;
int rs;
while(r-l>1){
mid=(l+r)/2;
sum=0;
rs=1;
for(i=1;i<=n;i++){
if(sum+a[i]<=mid)sum+=a[i];
else{
sum=a[i];
if(sum>mid){
rs=10000000;
}
rs++;
}
}
if(rs>m)l=mid;
else if(rs<=m)r=mid;
}
printf("%d\n",r);
}

Answer 1

　　额，这倒题对于我这种数学本身就不太好的人来说，太难了，头都想大了（智商是硬伤啊）！不过我倒是想把自己能想到的拿出来分享一下，仅供参考；

　　首先，我要提出一个错误，a[1000001]这样的写法是不对的，具体最大不太清楚，但肯定没有这么大的下标了，在这里的目的只是为也设置一下足够大的数组即可，不需要搞那么大！

　　好，下面正题开始：

       如题，设共有n个物品，m个人，生气程度最小的人生气程度为l,最大人的生气程度（即总共搬运物品）为r，第i个物品的重量为a[i]，第j个人生气程度为b[j](此处未用到)，假设只有最大和最小两种结果，则他们的平均值设为mid，若要使最大生气程度的人的生气值最小，则每个人的生气值都相等或近似相等且为最大值（因为如此一来，总数不变的情况下，得到的均值才最小），如下题解(注释)以此为基础；

scanf("%d%d",&n,&m); //输入n个物品和m个人
 for(i=1;i<=n;i++){  //输入n个物品各自的重量，依次序赋值，并保存总重量sum备用
  scanf("%d",&a[i]);
  sum+=a[i];
 }
 r=sum;                //将总数默认为最大生气值的默认值（实际是不是可能的）
 l=0;                  //将0作为最小生气的人的生气值（从这里的开始计算）
 int rs;               //找到的最大值的控制开关
 while(r-l>1){         //如果最大值和最小时之间相差小于1,则认为已找到最优解
  mid=(l+r)/2;         //算出中间值（缩小范围，中间的情况也是如此，没必要重复）
  sum=0;               //用以记录各个值间的大小大概关系
  rs=1;                
  for(i=1;i<=n;i++){
   if(sum+a[i]<=mid)sum+=a[i];//最开始时，各值不够大，让他们相加好了
   else{           //相加到一定程度后，转换另外一种算法，把他的值降小，重新计算
    sum=a[i];        
    if(sum>mid){   //如果这个值远远大于中间值，则基本上他就是最大值了，但亦不排除后面会有值比此大，因此未用break语句; 而是赋予开关一个很大的值
     rs=10000000;
    }
    rs++;         //开关加1，证明大于平均值的生气值又多了一个
   }
  }
  if(rs>m)l=mid;//生气值大于中间值的人数已大于总人数，也就是说大家可以再上一台阶
  else if(rs<=m)r=mid;  //否则，大家应当降一个级别，将中间值赋予最大值
 }

如此算下来，只要循环结束，以r为值即可得到最大生气的最小值（有点晕啊，没关系，多看看就好，看不懂也没关系，反正也不一定正确，哈哈）；

追问

嗯 非常谢谢你那么仔细的回答 但是我还有个小问题 就是为什么最大值和最小值之差小于1就认为找到最优解了呢？ 请再指点一下 谢谢

追答

好吧，既然你要这么问的话，我们就再挑两个毛病好了。1.这里的人真是奇怪呵，越生气搬的东西越搬得多（那是不是说老板越得罪你你越死命地干活呢？好神奇）；2.这里没有说重量单位，所以我们自己就以克为单位好了（但即使这样子相差1按理说也没有找到最优解，比1g小的还有很多，但天长地久有时尽，此解绵绵无绝期啊，我们只能说，这个1，已经是我们期望的会的值了）；题外话：每个人的生气值都相等其实才是真正的最小值，不是吗？那这道题就没有存在的意义了，直接等于n／m好了对吧！

哦，不对纠正一下，是sum（n）／m。