题意:
原题意比较啰嗦,大概的意思就是输入n个整数,然后将他们分成m段,要求求出这m段中最大和最小时候的情况。输出的时候段与段之间用"/"分离,当有多个解时,输出第一段值最小的,第一段相同时输出第二段值最小的解,以此类推。
思路:
一看到最大值最小,我就想到了二分,可以采取二分试探这个最大值,然后看是否能在这个最大值下能否分成m段,然后我们记录下二分过程中得到的那个满足要求的最小的值;对于这个题目的输出,我们可以采取贪心的策略:我们从最后一段开始分,在满足条件的情况使得后面的段尽量长;所谓满足条件是指这个段的和不超过上面求出的最大值,还有就是这一段分完以后要保证前面每一段都至少要有一个元素。第一点是很好控制的,对于第二点我们可以采取记录当前已分段数cnt,判断当前元素是否还可以分配到当前段;具体的,考虑分配到第i个元素那么前面最多还可以分成i+1段,则需要满足i+cnt>=num;
这个题还需要注意的是二分的写法,前面几次WA都是由于二分写的不对。下面的二分写法应该可以适用于这一种类型的题目。
代码如下:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define LL long long int a[550],cnt,n,num; int check(int sum) { int cnt=1; int temp=0; for(int i=n-1;i>=0;i--) { if(temp+a[i]>sum) { cnt++; temp=a[i]; if(cnt>num) return 0; } else temp+=a[i]; } return 1; } int main() { int i,j,t; scanf("%d%*c",&t); while(t--) { LL left=-1,right=0,mid; scanf("%d%d",&n,&num); for(i=0;i<n;i++) { scanf("%d",&a[i]); if(left<a[i]) left=a[i]; right+=a[i]; } int temp1; while(left <= right) { mid = left+(right-left)/2; if(check(mid)) temp1=right,right = mid-1; else left = mid+1; } int ans[550]; LL sum=temp1; LL temp=0,k=0,cnt=0; for(i=n-1;i>=0;i--) { if(temp+a[i]>sum||(num-cnt>i+1)) { cnt++; ans[k++]=i; temp=a[i]; } else temp+=a[i]; } for(i=0;i<n-1;i++) { printf("%d ",a[i]); for(j=0;j<k;j++) if(i==ans[j]) printf("/"),printf(" "); } printf("%d\n",a[n-1]); } return 0; }
原文:http://blog.csdn.net/acm_lkl/article/details/41365271