問題
http://community.topcoder.com/stat?c=problem_statement&pm=10682&rd=14145
不等式は複数与えられる。
与えられた不等式をできるだけ多く満たすような実数に対し
その満たす不等式の最大数を求める。
解き方
不等式の数Xは０～１０００になる。
よってー１～１００１まで0.5刻みの数を考え、このすべてに対し
不等式をどれだけ満たすか求めてあげればよい。
実数に対して配列のインデックスと一致させるために、
実数＊２＋２と変換してあげれば配列を利用できる。
コード
int num[2100];
class Inequalities {
public:
void calc(string str){
stringstream out(str);
string s1,s2;
int x;
out>>s1>>s2>>x;
if(s2=="<")for(double i=-1;i<x;i+=0.5)num[(int)(i*2+2)]++;
if(s2=="<=")for(double i=-1;i<=x;i+=0.5)num[(int)(i*2+2)]++;
if(s2=="=")num[x*2+2]++;
if(s2==">")for(double i=x+0.5;i<=1005;i+=0.5)num[(int)(i*2+2)]++;
if(s2==">=")for(double i=x;i<=1005;i+=0.5)num[(int)(i*2+2)]++;
}
int maximumSubset(vector<string> inequalities) {
memset(num,0,sizeof(num));
FORE(i,0,inequalities.size()){
calc(inequalities[i]);
}
int ret=0;
FORE(i,0,2100){
ret=max(ret,num[i]);
}
return ret;
}
};
class Inequalities {
public:
void calc(string str){
stringstream out(str);
string s1,s2;
int x;
out>>s1>>s2>>x;
if(s2=="<")for(double i=-1;i<x;i+=0.5)num[(int)(i*2+2)]++;
if(s2=="<=")for(double i=-1;i<=x;i+=0.5)num[(int)(i*2+2)]++;
if(s2=="=")num[x*2+2]++;
if(s2==">")for(double i=x+0.5;i<=1005;i+=0.5)num[(int)(i*2+2)]++;
if(s2==">=")for(double i=x;i<=1005;i+=0.5)num[(int)(i*2+2)]++;
}
int maximumSubset(vector<string> inequalities) {
memset(num,0,sizeof(num));
FORE(i,0,inequalities.size()){
calc(inequalities[i]);
}
int ret=0;
FORE(i,0,2100){
ret=max(ret,num[i]);
}
return ret;
}
};