TIOJ 1432 骨牌遊戲

[二分搜]
:3

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int inp[1003];
int max;
int n,k;
int check(int r)
{
 if(r<max)
  return false;
 int kcnt=0;int cnt=0;
 for(int lx=1;lx<=n;lx++)
 {
  cnt+=inp[lx];
  if(cnt>r)
  {
   cnt=inp[lx];
   kcnt++;
  }
  else if((cnt==r)&&(lx<n))
  {
   cnt=0;
   kcnt++;
  }
 }
 return (kcnt<=k);
}
int main()
{
 int sum=0;
 while(scanf("%d %d",&n,&k)==2)
 {
  sum=0;
  if((k+n)==0)
   break;
  max=0;
  for(int lx=1;lx<=n;lx++)
  {
   scanf("%d",&inp[lx]);
   max=fMax(max,inp[lx]);
   sum+=inp[lx];
  }

  int down=max;
  int up=sum;
  int res=0;
  int prc=0;
  while(1)
  {
   if(down==up)
   {
    res=down;
    break;
   }
   if(down==(up-1))
   {
    if(check(down))
     res=down;
    else
     res=up;
    break;
   }
   prc=(up+down)/2;
   if(check(prc))
    up=prc;
   else
    down=prc;
  }
  printf("%d\n",res);
 }
 return 0;
}