SRM 528 div1 easy: Cut - mayoko’s diary

問題

解法

10 の倍数のうなぎは例えば 30 -> 20, 10 -> 10, 10, 10 というように, n*10 のうなぎは n-1 回の切断で n 個の長さ 10 のうなぎを錬成出来ます。ということで, 10 の倍数で短いうなぎから切断していくと, 切る回数が少なくてもたくさん長さ 10 のうなぎを錬成できる可能性があります。これが明らかに最適なので, 次のように貪欲に切断していけば良いです。

・10 の倍数の長さで短いものから長さ 10 にするように切っていく。
・それでも切る回数が余ったら長さが 10 の倍数でないうなぎを使って長さ 10 のうなぎを錬成する。

class Cut {
public:
    int getMaximum(vector <int> eelLengths, int maxCuts) {
        int n = eelLengths.size();
        sort(eelLengths.begin(), eelLengths.end());
        vector<int> ten, other;
        for (int i = 0; i < n; i++) {
            if (eelLengths[i]%10 == 0) ten.push_back(eelLengths[i]);
            else other.push_back(eelLengths[i]);
        }
        int ans = 0, m = ten.size();
        for (int i = 0; i < m; i++) {
            int tmp = ten[i];
            while (maxCuts > 0 && tmp > 10) {
                ans++;
                tmp -= 10;
                maxCuts--;
            }
            if (tmp == 10) ans++;
        }
        for (int i = 0; i < n-m; i++) {
            int tmp = other[i];
            while (maxCuts > 0 && tmp > 10) {
                ans++;
                tmp -= 10;
                maxCuts--;
            }
        }
        return ans;
    }
};