首页 > 代码库 > 多校第六场 1003 hdu 5355 Cake(贪心)

多校第六场 1003 hdu 5355 Cake(贪心)

题目链接:(数据加强后wa了)

hdu 5355


题目大意:

给出一个蛋糕。切成1~n大小的n块。问是否能在不继续分割的情况下拼凑出m等份。


题目分析:

  • 首先我们是可以知道每份蛋糕的尺寸的,利用n*(n+1)/2m可以算出来,假设不能整除的话,那么一定无解。

  • 然后我们考虑怎样构造一组解,对于一块蛋糕,我想到了一个贪心策咯,尽量选择最大块的蛋糕,由于假设能选可是不选这块蛋糕,那么也一定是通过选取小块的蛋糕来拼凑出这块蛋糕的大小,可是假设小的拼凑出了这块,那么就不能用于拼凑其它的蛋糕,显然选择最大的这块是最优的,由于他不可能被用来拼凑出其它的蛋糕。所以当前选取它不会造成其它的蛋糕拼凑受影响,所以我们这样选取一定是正确的。

AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;
int t;
LL n,m;
vector<int> v[20];
int mark[100007];

int main ( )
{
    scanf ( "%d" , &t );
    while ( t-- )
    {
        memset ( mark , 0 , sizeof ( mark ));
        for ( int i = 0 ; i < 20 ; i++ )
            v[i].clear();
        scanf ( "%I64d%I64d" , &n , &m );
        LL ans = n*(n+1)/2;
        LL num = ans/m;
        if ( ans%m ||  num < n )
        {
            puts ( "NO" );
            continue;
        }
        LL r = n;
        int i;
        for ( i = 0 ; i < m ; i++ )
        {
            //cout <<n << " " << num << " "<< i << " " << r << endl;
            LL temp = num;
            bool flag = true;
            while ( mark[r] && r > 1 ) r--;
            while ( temp >= r && !mark[r] )
            {
                v[i].push_back ( r );
                mark[r] = true;
                temp -= r;
                r--;
                if ( r == 0 ) break;
                while ( mark[r] && r > 1 ) r--;
            }
            if ( temp == 0 )
            {
                flag = false;
            }
            else if ( !mark[temp] )
            {
                v[i].push_back ( temp );
                mark[temp] = true;
                flag = false;
            }
            else
            {
                while ( true )
                {
                    bool finish = false;
                    for ( int j = temp ; j > 0 ; j-- )
                    {
                        if ( !mark[j])
                        {
                            mark[j] = true;
                            v[i].push_back ( j );
                            temp -= j;
                            finish = true;
                            break;
                        }
                    }
                    if ( !finish ) break;
                    if ( temp == 0 )
                    {
                        flag = false;
                        break;
                    }
                }
            }
            if ( flag ) break;
        }
        if ( i == m )
        {
            puts ( "YES" );
            for ( int i = 0 ; i < m ; i++ )
            {
                printf ( "%d" , v[i].size() );
                for ( int j = 0 ; j < v[i].size() ; j++ )
                    printf ( " %d" , v[i][j] );
                puts ( "");
            }
        }
        else puts ( "NO" );
    }
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

多校第六场 1003 hdu 5355 Cake(贪心)