首页 > 代码库 > UVa 714,Copying Books

UVa 714,Copying Books

最大值最小化

1A

要用long long,因为计算sum的时候int会超。  

值得一提的是,给的第二组样例很好。二分找到解后k有可能用不完。

如果有多解,s(1)应该尽量小,换句话说也就是s(2)要最大,利用栈倒序输出解决问题。

#include <iostream>#include <cstdio>#include <algorithm>#include <stack>#include <cstring>#define maxn 500+10using namespace std;long long m,k;long long maxx,minx;long long a[maxn],sum[maxn];long long init(){    cin>>m>>k;    memset(a,0,sizeof(a));    memset(sum,0,sizeof(sum));//sum[i],前i项的和     minx=0;    for (long long i=1;i<=m;i++)        {cin>>a[i];sum[i]+=sum[i-1]+a[i];minx=max((long long)minx,a[i]);}    maxx=sum[m];}long long work(long long x){    long long last=0;    long long t=k;    for (long long i=1;i<=m;i++){        if (sum[i]-sum[last]<=x&&i<m)    continue;        if (i==m&&sum[i]-sum[last]>x&&t==1) return 0;        t--;        last=i-1;    }    if (t<0) return 0;        else return 1;}long long printf(long long x){    long long f=0;    long long t=k-1;    stack<long long> stk;    long long i=m;    while(i>0){        f+=a[i];        if (f>x){            stk.push(0);            f=a[i];            t--;        }        stk.push(a[i]);        i--;    }    cout<<stk.top();    stk.pop();    while (!stk.empty()){        long long u=stk.top();        stk.pop();        if (!u) cout<<" /";            else if (t&&stk.top()) {                t--;                cout<<" "<<u;                cout<<" /";            }            else cout<<" "<<u;    }        cout<<endl;}int main(){    long long T;    long long x;    cin>>T;    while (T--){        init();        while ((maxx-minx)>1){//二分查找             x=(minx+maxx)/2;            if (work(x)) maxx=x;                else minx=x;         }        printf(maxx);    }}//uva 714
View Code

 

UVa 714,Copying Books