有 n 个不等式用来描述变量 x ,其中一些是相互矛盾的,你来选取一个关于 x 的值,让这 n 个不等式中,产生的矛盾最少(即满足条件的不等式最多),输出最少的矛盾数量。
其中 L v 表示 x<=v , G v 表示 x>=v
#include<bits/stdc++.h>
using namespace std;
int br[1010],sr[1010],n,s1,s2,ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
char op;
int x;
cin>>op>>x;
if(op=='G'){
s1++;
br[s1]=x;
}
else{
s2++;
sr[s2]=x;
}
}
sort(br+1,br+s1+1);
sort(sr+1,sr+s2+1);
int l=1;
for(int i=1;i<=s1;i++){
int tmp=0;
while(sr[l]<br[i]&&l<=s2){
l++;
}
tmp=i+s2-l+1;
ans=max(ans,tmp);
}
cout<<n-ans;
return 0;
}