SRM528 Div1 Easy - Cut
問題
うなぎがn匹あり、i匹目の長さはl[i]である
c回までうなぎを切って長さ10のうなぎをなるべく多く作りたい
最大で何本作れるか
1 <= 50 <= n
1 <= l[i] <= 1000
1 <= c <= 1000
解法
長さ10のうなぎは基本的には単純に1回切るごとに1本作れる
各うなぎからは最大でc[i]/10個まで作れる
ただし長さcが10の倍数であるようなうなぎは、c/10-1回切ると1本多くできてc/10本になる
このことから、長さが10の倍数のうなぎを短いものから優先的に切るのが最善とわかる
class Cut { public: int getMaximum(vector<int> l, int c) { vector<int> x, y; each(i,l) (i%10==0 ? x : y).push_back(i/10); sort(all(x)); int res = 0; each(i,x) { if (i-1<=c) res += i, c -= i-1; else res += c, c = 0; } each(i,y) res += min(c,i), c -= min(c,i); return res; } };