SRM 528 250pt : Cut

問題概要

長さL[i]のうなぎがある。これをM(<1000)回以下切断して長さ10のうなぎをどれだけたくさん作ることができるか求める問題。

解法

20を切るのが得なので、10の倍数の小さいものから優先的に処理をしていく。もっと早くとくこともできるけど、分かりやすく書くのを最優先すべき。

修正したコード

#include <vector>
#include <algorithm>
using namespace std;

struct Cut {

	int getMaximum(vector <int> ls, int maxCuts) {
		const int N = ls.size();

		int ans = 0;
		for(int i=0; i<maxCuts; i++){
			sort(ls.begin(), ls.end());
			bool update = false;

			for(int j=0; j<N; j++)if(ls[j] > 10 && ls[j]%10 == 0){
				update = true;
				ans++;
				ls[j] -= 10;
				break;
			}

			if(!update){
				for(int j=0; j<N; j++)if(ls[j] > 10){
					update = true;
					ans++;
					ls[j] -= 10;
					break;
				}
			}

			if(!update){
				break;
			}
		}

		for(int i=0; i<N; i++){
			if(ls[i] == 10){
				ans++;
			}
		}

		return ans;
	}

};