SRM459 Div1 Easy(250), Div2 Medium(500) Inequalities
xの範囲が狭いので、xの値を変えて成り立つ不等号を数える。
#include <string> #include <vector> #include <sstream> #include <algorithm> using namespace std; class Inequalities { public: int maximumSubset( vector <string> inequalities ); }; int Inequalities::maximumSubset( vector <string> inequalities ) { int n = (int)inequalities.size(); vector<string> E(n); vector<int> C(n); for ( int i=0; i<n; i++ ) { stringstream s( inequalities[i].substr(1) ); s >> E[i] >> C[i]; C[i] *= 2; } int m = 0; for ( int x=*min_element(C.begin(),C.end())-1; x<=*max_element(C.begin(),C.end())+1; x++ ) { int c = 0; for ( int i=0; i<n; i++ ) if ( E[i] == "<" && x < C[i] || E[i] == "<=" && x <= C[i] || E[i] == "=" && x == C[i] || E[i] == ">" && x > C[i] || E[i] == ">=" && x >= C[i] ) c++; m = max( m, c ); } return m; }