SRM506 Div1 Easy(250), Div2 Medium(500) SlimeXSlimesCity
ある街aの名前を最終的な街の名前にしようとするときは、なるべく小さい街からaに合併していくのが最善。全ての街について最終的な街の名前をその街の名前にできるか調べる。
#include <vector> #include <algorithm> using namespace std; class SlimeXSlimesCity{public: int merge( vector <int> population ) { int n = (int)population.size(); int ans = 0; sort(population.begin(),population.end()); for ( int i=0; i<n; i++ ) { bool f = true; long long t = population[i]; for ( int j=0; j<n; j++ ) if ( j != i ) { if ( t < population[j] ) f = false; t += population[j]; } if ( f ) ans++; } return ans; }};