首页 > 代码库 > hihocoder 1341 Constraint Checker【string】

hihocoder 1341 Constraint Checker【string】

hihocoder 1341

解释:
这道题题目还是比较容易理解,就是根据输入的若干个不等式,校验后面输入的数据是否都满足前面的不等式,满足就输出Yes,只要有一个不满足就输出No。如“A<B<=E,3<=E<5”这个两个关系式,对于输入A=1,B=2,E=3肯定满足,因为1<2<=3,3<=3<5。而A=3, B=5,E=10就不满足,因为3<=10<5不成立。

思路:

将一串表达式拆分为每两个数比较大小,读取操作数[字母/数字], 读取运算符[‘<’/‘<=’]

#include <iostream>#include <algorithm>#include <map>#include <string>#include <string.h>#include <ctype.h>using namespace std;map<char,int> mp;string c[20];bool used[26];bool ok(int a, string &op, int b){    if(op=="<") return a<b;    return a<=b;}int get_val(string &s, int &i){    int res=0;    for(; s[i] && isdigit(s[i]) && !isalpha(s[i]); res*=10, res+=s[i++]-‘0‘);    if(isalpha(s[i])) res=mp[s[i++]];    return res;}string get_op(string &s, int &i){    string res;    for(; s[i] && ispunct(s[i]); res+=s[i++]);    return res;}bool check(int n){    int a, b;    string op;    for(int i=0; i<n; i++){        int j=0;        a=get_val(c[i], j);        for(;;){            op=get_op(c[i], j);            if(op=="") break;            b=get_val(c[i], j);            if(!ok(a, op, b)) return false;            a=b;        }    }    return true;}int main(){    int n, T;    cin>>n;    for(int i=0; i<n; i++){        cin>>c[i];        for(auto x:c[i])            if(isalpha(x)) used[x-‘A‘]=true;    }    int nv=0;    for(int i=0; i<26; i++) nv+=used[i];        for(cin>>T; T--; ){        for(int i=0; i<nv; i++){            char x;            int v;            cin>>x>>v;            mp[x]=v;        }        puts(check(n)?"Yes":"No");    }}

hihocoder 1341 Constraint Checker【string】