经典的判定。对N个正整数的k-划分，要求的是划分中最大数的最小值。如有相同最小值，使前面的划分和最小。

这题的思路是穷举这个最小值，然后计算是否满足k划分。设当前的划分数为x，mx得到的是满足x<=k的最小值。穷举的过程可以用二分。

判定计算采用的是贪婪算法，从后向前，尽量使后面的划分之和在要求判定的值范围内最大。同时把划分处b[i]置1。

另外，有可能出现mx的划分数x<k，而mx-1的划分数x>k的情况。此时为了使前面的划分最小，只消将前面几个空闲的b[i]置1即可。

#include <cstdio>
#include <string>

int m, n, t, b[501];    //seperate

double a[501], sum, mx, mn;      //book

int check ( double chk_n )
{
    int i, total = 0;
    double t_sum = 0;
    memset ( b, 0, sizeof ( b ) );
    for ( i = n - 1; i >= 0; i -- )
    {
        t_sum += a[i];
        if ( t_sum > chk_n )
        {
            t_sum = a[i];
            b[i] = 1;
            total ++;
        }
    }
    return total + 1;
}

void print ()
{
    int i = 0;
    int x = check ( mx );
 //printf ( "%d\n", x );
 x = t - x;

    while ( x )
 {
  if ( !b[i] )
  {
   b[i] = 1;
   x --;
  }
  i ++;
 }

    for ( i = 0; i < n; i ++ )
    {
        if ( i )
        {
            printf ( " " );
        }
        printf ( "%0.0f", a[i] );
        if ( b[i] )
        {
            printf ( " /" );
        }
    }
    printf ( "\n" );
}

void init ()
{
    int i;
    sum = 0;
    mn = 0;
    for ( i = 0; i < n; i ++ )
    {
        scanf ( "%lf", &a[i] );
        sum += a[i];
        if ( mn < a[i] )
        {
            mn = a[i];
        }
    }
    mx = sum;
}

void b_search ()
{
    double mid = ( mn + mx ) / 2;
    while ( mn < mx )
    {
        int x = check ( mid );
        //printf ( "%I64d %I64d %I64d\n", mx, mn, mid );
        if ( x > t )
        {
            mn = mid + 1;
        }
        else if ( x <= t )
        {
            mx = mid;
        }
        mid = ( mn + mx ) / 2;
    }
}

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    scanf ( "%d", &m );
    int i;
    for ( i = 0; i < m; i ++ )
    {
        scanf ( "%d %d", &n, &t );
        init ();
        b_search ();
        print ();
    }
    return 0;
}

评论