TopCoder SRM 528 Div1 Easy Cut
問題
n匹のうなぎがいて、それぞれの長さはeelLengths[i]である。
このうなぎをmaxCut回以下だけ切って長さがちょうど10であるようなうなぎを出来るだけ多く作りたい。
最大でいくつ長さ10のうなぎができるか求めよ。
制約条件
n≦50
eelLengths[i]≦1000
maxCut≦1000
方針
長さが10の倍数のうなぎから優先的に切っていくだけ。
ソースコード
bool cmp(int a,int b){ if((a%10==0)^(b%10==0))return a%10==0; return a<b; } class Cut { public: int getMaximum(vector <int> eelLengths, int maxCuts) { int ans=0; sort(all(eelLengths),cmp); rep(i,eelLengths.size()){ int t=max(0,(eelLengths[i]+9)/10-1); //切断回数 t=min(t,maxCuts); maxCuts-=t; if(eelLengths[i]==(t+1)*10)ans+=t+1; //最後の切れ端が10のとき else ans+=t; } return ans; } };