首页 > 代码库 > 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
UVa 714,Copying Books
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。