Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
二分+贪心~ac代码#include<iostream> #include<cstdio> #include<algorithm> #define PB push_back #define MP make_pair using namespace std; typedef long long LL; typedef pair<int,int> PII; #define PI acos((double)-1) #define E exp(double(1)) const int K=1000+9; int a[K],n,m,d[K]; bool check(int k) { for(int i=1,sum=0,seg=0;i<=n;i++) { sum+=a[i]; if(sum>k) seg++,sum=a[i]; if(seg>=m||sum>k) return 0; } return 1; } int main(void) { int t;cin>>t; while(t--) { int ans,l,r,mid; l=0,r=0; cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]),r+=a[i]; while(l<=r) { mid=l+r>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } for(int i=n,sum=0,cnt=--m;i;i--) { if(i==cnt) { for(int j=1;j<=i;j++) d[j]=j; break; } sum+=a[i]; if(sum>ans) d[cnt--]=i,sum=a[i]; } for(int i=1,j=1;i<=m;i++) { while(j<=d[i]) printf("%d ",a[j++]); printf("/ "); } for(int i=d[m]+1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' '); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator