[POJ 3273 Monthly Expense]二分答案

【题目大意】

给定一个数组A[i]，1<=a[i]<=10000

求把它分成M份，每份的和不超过一个值K。

问K最小是多少？

【算法分析】

注意到A[i]都是正数，所以我们可以二分答案，然后线性贪心判断即可。

如果A[i]存在负数的话，这个算法就不正确了。

【其它】

1WA，1A。悲剧，忘了删文件。

另外一开始想了挺久的。。。最主要是读题不够仔细，没看到那个A[i]>=1

【CODE】

#include #include #include typedef long long LL;
int m,n;
int a[101111],Max=0;

bool flag(LL limit){
    int num=1;
    LL sum=a[1];
    for (int i=2;i<=n;i++)
      if (sum+a[i]>limit){
          num++;
          sum=a[i];
      }
      else sum+=a[i];
    if (num>m) return false;
    return true;
}   

int main(){
    scanf("%d%d",&n,&m);
    LL sum=0;
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (a[i]>Max) Max=a[i];
        sum+=a[i];
    }   
    LL l=Max,r=sum,mid;
    while (l        mid=(l+r)/2;
        if (flag(mid)) r=mid;
                  else l=mid+1;
    }
    printf("%lldn",l);
}