SRM506 Div1 Easy - SlimeXSlimesCity
問題
n個の街があり街iの人口はa[i]
好きな順で街を合併して新しい街を作り、人口が大きかった方(同じなら好きな方)の名前をつける
最後にまとまる1つの街の名前としてあり得るものの個数を求める
解法
各街の視点に立って、人口が自分以下の街を貪欲に吸収していって全部吸収できたら答えに+1
実装
人口の昇順にソートして、i番目の街の視点ではまず[0,i)を全部吸収できて、あとは(i,n)を順に吸収できるか調べればいい
b(ase): Σa[0,i]
s(um): 街iの現在の人口
class SlimeXSlimesCity { public: int merge(vector<int> a) { ll n = a.size(), res = 0, b = 0, s = 0; sort(all(a)); rep(i,n) { b += a[i], s = b; bool ng = 0; reps(j,i+1,n) { if (a[j]<=s) s += a[j]; else ng = 1; } if (!ng) res++; } return res; } };