首页 > 其他 > 详细

uva--714+二分(最大值最小化问题)

时间:2014-11-22 00:48:58      阅读:665      评论:0      收藏:0      [点我收藏+]

题意:

     原题意比较啰嗦,大概的意思就是输入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;
}


uva--714+二分(最大值最小化问题)

原文:http://blog.csdn.net/acm_lkl/article/details/41365271

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!