SRM528 Div1 Easy(250), Div2 Medium(500) Cut

TopCoder

Cut

ウナギの長さが10kならば、k-1回切ってk本の長さ10のウナギが得られる。それ以外の場合は切った回数のウナギが得られる。長さが10の倍数で短いウナギから順に切っていけば良い。

#include <vector>
#include <algorithm>
using namespace std;

bool cmp( int a, int b ) { return a%10*10000+a < b%10*10000+b; }

class Cut{public:
int getMaximum( vector <int> eelLengths, int maxCuts )
{
    int n = (int)eelLengths.size();
    sort( eelLengths.begin(), eelLengths.end(), cmp );

    int ans = 0;

    for ( int i=0; i<n; i++ )
    {
        if ( eelLengths[i]%10==0 && eelLengths[i]/10-1<=maxCuts )
        {
            ans += eelLengths[i]/10;
            maxCuts -= eelLengths[i]/10-1;
        }
        else
        {
            int t = min( eelLengths[i]/10, maxCuts );
            ans += t;
            maxCuts -= t;
        }
    }

    return ans;
}};