Aizu Online Judge 0181 Persistence

■0181 Persistence

二分探索．

本棚の幅をbとし，幅bの本棚に全て本を収納出来ることをC(b)で表す．
この問題における答えは，C(b)となる最小のb(=b_min)であり，C(b)であるかどうかは容易に求まる，かつb<b_minなるbについては，C(b)は成立しないので二分探索を適用することが出来る．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int m, n;  
17.  int[] a;  
18.   
19.  void run(){  
20.   for(;;){  
21.    m=sc.nextInt();  
22.    n=sc.nextInt();  
23.    if((m|n)==0){  
24.     break;  
25.    }  
26.    a=new int[n];  
27.    for(int i=0; i<n; i++){  
28.     a[i]=sc.nextInt();  
29.    }  
30.    solve();  
31.   }  
32.  }  
33.   
34.  void solve(){  
35.   int left=0, right=1500000;  
36.   for(int i=0; i<100; i++){  
37.    int mid=(left+right)/2;  
38.    if(check(mid)){  
39.     right=mid;  
40.    }else{  
41.     left=mid;  
42.    }  
43.   }  
44.   println(""+right);  
45.  }  
46.   
47.  boolean check(int b){  
48.   int d=1;  
49.   int sum=0;  
50.   for(int i=0; i<n; i++){  
51.    if(a[i]>b){  
52.     return false;  
53.    }  
54.    sum+=a[i];  
55.    if(sum>b){  
56.     sum=a[i];  
57.     d++;  
58.    }  
59.   }  
60.   return d<=m;  
61.  }  
62.   
63.  void debug(Object... os){  
64.   System.err.println(Arrays.deepToString(os));  
65.  }  
66.   
67.  void print(String s){  
68.   System.out.print(s);  
69.  }  
70.   
71.  void println(String s){  
72.   System.out.println(s);  
73.  }  
74.   
75.  public static void main(String[] args){  
76.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
77.   new Main().run();  
78.  }  
79. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[] a;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int left=0, right=1500000;
  for(int i=0; i<100; i++){
   int mid=(left+right)/2;
   if(check(mid)){
    right=mid;
   }else{
    left=mid;
   }
  }
  println(""+right);
 }

 boolean check(int b){
  int d=1;
  int sum=0;
  for(int i=0; i<n; i++){
   if(a[i]>b){
    return false;
   }
   sum+=a[i];
   if(sum>b){
    sum=a[i];
    d++;
   }
  }
  return d<=m;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}