SRM #528 Div.1 Easy - Cut
概要
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; } };