UVa11413 - Fill the Containers(最大值最小化问题)

importjava.io.IOException;
importjava.io.FileInputStream;
importjava.io.InputStreamReader;
importjava.io.BufferedReader;
importjava.io.PrintWriter;
importjava.io.OutputStreamWriter;
importjava.io.StreamTokenizer;
publicclassMain{
publicstaticbooleanDEBUG=false;
publicBufferedReadercin;
publicPrintWritercout;
publicStreamTokenizertokenizer;
publicintn, m, sum;
publicint[] a;
publicvoidinit()
    {
try {
if (DEBUG) {
cin=newBufferedReader(newInputStreamReader(
newFileInputStream("d:\\OJ\\uva_in.txt")));
            } else {
cin=newBufferedReader(newInputStreamReader(System.in));
            }
        } catch (IOExceptione) {
        }
cout=newPrintWriter(newOutputStreamWriter(System.out));
tokenizer=newStreamTokenizer(cin);
    }
publicStringnext()
    {
try {
tokenizer.nextToken();
if (tokenizer.ttype==StreamTokenizer.TT_EOF)
returnnull;
elseif (tokenizer.ttype==StreamTokenizer.TT_WORD)
returntokenizer.sval;
elseif (tokenizer.ttype==StreamTokenizer.TT_NUMBER) 
returnString.valueOf((int)tokenizer.nval);
        } catch (IOExceptione) {
        }
returnnull;
    }
publicbooleaninput()
    {
try {
n=Integer.parseInt(next());
a=newint[n];
m=Integer.parseInt(next());
for (inti=0; i<n; i++) {
a[i] =Integer.parseInt(next());
sum+=a[i];
            }
returntrue;
        } catch (Exceptione) {
returnfalse;
        }
    }
privatebooleancheck(intnum)
    {
intcnt=0;
ints=0;
for (inti=0; i<n; i++) {
if (a[i] >num) returnfalse;
if (s+a[i] >num) {
cnt++;
s=0;
            }
s+=a[i];
        }
if (cnt<=m-1) returntrue;
returnfalse;
    }
publicvoidsolve()
    {
intlow=0, high=sum;
while (low<high) {
intmid= (low+high) >>1;
if (check(mid)) {
high=mid;
            } else {
low=mid+1;
            }
        }
cout.println(low);
cout.flush();
    }
publicstaticvoidmain(String[] args)
    {
try {
Mainsolver=newMain();
solver.init();
while (solver.input()) {
solver.solve();
            }
        } catch (Exceptione) {
        }
    }
}