经典的判定。对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;} 2263160 2007-03-11 22:06:03 Accepted 2002 C++ 00:00.05 400K Crux.D

评论