SRM 528 div1 easy: Cut
解法
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; } };