SRM #528 Div.1 Easy - Cut

出典

TopCoder Single Round Match 528 - Div. 1 Easy
TopCoder Single Round Match 528 - Div. 2 Medium

概要

n個の数をk回分割して10は最大で何個作れるか
(10で割った余り, 10で割った商)でソートしてgreedyに切っていく
ソートしたところまでは良かったが、切って行く所でバグった模様(Systest failed)

ソース

#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

class Cut {
private:

public:
	int getMaximum(vector<int> lengths, int cuts) {
		int n = lengths.size();
		vector<pair<int, int> > x(n);
	
		for (int i = 0; i < n; i++) {
			x[i] = pair<int, int>(lengths[i] % 10, lengths[i] / 10);
		}
		sort(x.begin(), x.end());
		
		int ans = 0;
		for(int i = 0; i < n && cuts > 0; i++) {
			if (x[i].first == 0) {
				if (x[i].second - 1 <= cuts) {
					ans += x[i].second;
					cuts -= x[i].second - 1;
				}
				else {
					ans += cuts;
					cuts = 0;
				}
			}
			else {
				ans += min(cuts, x[i].second);
				cuts -= x[i].second;
			}
		}
		
		return ans;
	}

};