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