WIKIOI 3162抄書問題の問題解と分析

【タイトルリンク】:
          http://www.wikioi.com/problem/3162/
【分析】:
         これは経典の最大値の最小を求める問題で、二分の答えを使います.一人一人の写本の最大値を二分し、後からできるだけ多く写させ、本全体を写すと上界を下げ、本を写さずに全員を回し終わると下界を上げ、上界=下界になると退出し、同じ方法で後ろから本を取る
【コード】:

#include
#include
#include
#include
#include
using namespace std;
#define MAX 10001
#define IMAX 21474836
int M,K,a[MAX],min1=IMAX,max1=0,x[MAX],y[MAX],ans;
bool check(int x)
{
      int sum=0,now=M;
      for(int i=K;i>=1;i--)
      {
            sum=0;
            while(sum+a[now]<=x && now>0)
            {
                  sum+=a[now];
                  now--;
            }
            if(now==0)   return true;
      }
      return false;
}
void work()
{
      int left=min1,right=max1;
      while(left
                  right=middle;
            else left=middle+1;//        
      }
      ans=left=right;
}
int main()
{
      //freopen("input.in","r",stdin);
	  //freopen("output.out","w",stdout); 
	  scanf("%d%d",&M,&K);
	  for(int i=1;i<=M;i++)
	  {
	        scanf("%d",&a[i]);
	        min1=min(a[i],min1);
	        max1+=abs(a[i]);
      }
      work();
      
      int sum=0,now=M;
      for(int i=K;i>=1;i--)
      {
            sum=0;
            y[i]=now;
            while(sum+a[now]<=ans && now>=i)
            {
                  sum+=a[now];
                  now--;
            }
            x[i]=now+1;
      }
      for(int i=1;i<=K;i++)
            printf("%d %d
",x[i],y[i]);
      return 0;
}

 
転載して出典を明記する:http://blog.csdn.net/u011400953