P7923 「EVOI-RD2」昕昕的不等式组 题解

· · 题解

这道橙模拟通过率出奇的低，可能说明大家对于细节的处理有一定疏漏。

先来读题，这是一道模拟题，要给你 n 个关于 x 的最简不等式，求出它们的交集并用最简不等式的形式输出。

我们用一个结构体 ine 来存储不等式的信息：

struct ine
{
    int val;//不等式右侧常数的值
    bool isg;//符号是否为>或≥
    bool eq;//符号是否为≥或≤
};

并且定义一个 ine 类型的并以 val 为关键字的结构体优先队列，比较函数部分代码如下：

struct cmp
{
    bool operator()(ine x,ine y)
    {
        if (x.val!=y.val)return x.val>y.val;
        //下面是常数相等时的情况
        if (x.isg!=y.isg)return !x.isg;//>、≥排在<、≤前
        if (x.isg)return !x.eq;//≥排在>前
        return x.eq;//<排在≤前
    }
};

这样我们可以保证在分析不等关系时从队头抽取不等关系改变永远不会使原先确定的交集边界产生错误，并保证上界条件与第一次出现的小于（等于）关系条件相同。

再定义几个用于描述交集的变量：

int sval;//交集下界
int gval;//交集上界
bool seq;//下界是否能取等
bool geq;//上界是否能取等

然后我们在主程序中每次取出优先队列队头的不等关系并分情况讨论，伪代码如下（个人认为伪代码比自然语言讲解更有条理）：

if 是小于关系 且 未出现过小于关系
    上界条件=当前不等关系条件

if 出现过小于关系 且 当前是大于（等于）关系
    输出 "No Answer!" 并结束程序

if 当前是大于关系 且 未出现过小于关系
    下界条件=当前不等关系条件

由于我们前面对每个关系排序的第一关键字是 val，而老师又教过我们大大小小解没了，所以易知若有任何大于关系在优先队列中排在小于关系后面就一定无解。

而输出时也要分情况讨论，伪代码如下：

if sval==gval
{
    if seq==geq==1
        输出 x=sval 并结束程序
    else
        输出 "No Answer!" 并结束程序
}

if 上界无限定条件
    输出 x>(≥)sval 并结束程序

if 下界无限定条件
    输出 x<(≤)gval 并结束程序

其他情况
    输出 sval<(≤)x<(≤)gval 并结束程序

这样就喜提AC了。模拟题最重要的是细节和各种状况的处理，一定要仔细考虑所有的状况如何处理、所有的细节如何判断。另外一些模拟题的输入和（或）输出也很难缠。

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct ine
{
    int val;
    bool isg,eq;
};
struct cmp
{
    bool operator()(ine x,ine y)
    {
        if (x.val!=y.val)return x.val>y.val;
        if (x.isg!=y.isg)return !x.isg;
        if (x.isg)return !x.eq;
        return x.eq;
    }
};
priority_queue<ine,vector<ine>,cmp >q;
int n,sval,gval;
bool seq,geq;
char c;
string s;
int main()
{
    cin>>n>>c;
    for (int i=0;i<n;i++)
    {
        ine t;
        t.val=0;
        cin>>s;
        int sz=s.size(),now=2;
        bool negative=0;
        if (s[1]=='>')t.isg=1;
        else t.isg=0;
        if (s[2]=='=')
        {
            t.eq=1;
            now=3;
        }
        else t.eq=0;
        if (s[now]=='-')
        {
            now++;
            negative=1;
        }
        for (;now<sz;now++)t.val=t.val*10+s[now]-'0';
        if (negative)t.val*=-1;
        q.push(t);
    }
    bool smaller=0,isg=0;
    while (!q.empty())
    {
        ine t=q.top();
        q.pop();
        if (!t.isg)
        {
            if (!smaller)
            {
                if (t.eq)geq=1;
                gval=t.val;
            }
            smaller=1;
        }
        else if (smaller)
        {
            cout<<"No Answer!";
            return 0;
        }
        else
        {
            isg=1;
            if (t.eq)seq=1;
            else seq=0;
            sval=t.val;
        }
    }
    if (sval==gval)
    {
        if (seq&&geq)cout<<c<<'='<<sval;
        else cout<<"No Answer!";
        return 0;
    }
    if (!isg)
    {
        cout<<c<<'<';
        if (geq)cout<<'=';
        cout<<gval;
        return 0;
    }
    if (!smaller)
    {
        cout<<c<<'>';
        if (seq)cout<<'=';
        cout<<sval;
        return 0;
    }
    cout<<sval<<'<';
    if (seq)cout<<'=';
    cout<<c;
    cout<<'<';
    if (geq)cout<<'=';
    cout<<gval;
}

推荐模拟题：P4711 「化学」相对分子质量、P1928 外星密码