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;
	}
};