Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

二分+贪心~ac代码

Posted by weeping at 2016-08-20 01:24:50 on Problem 1505
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator