P6123 [NEERC2016] Hard Refactoring 题解

· · 题解

题意

题目要我们求一个不等式组的解集，并以最简洁的方式输出。我们可以抽象成有多个区间，题目要我们合并区间，若这些区间覆盖了 [-2^{15},2^{15}-1] 则输出 true ，若这些区间的左端点全部都大于右端点（即 a \le x \le b,a > b，此情况无解），则输出 false。

思路

处理出每一个约束条件所代表的区间的左端点和右端点，如果一行只有一个约束条件，那么就将缺少的那个端点设为 -2^{15} 或 2^{15}-1（举例：x <= 2 转化为左端点为 -2^{15}，右端点为 2 的区间）。 处理出所有区间后进行排序，然后合并相交的区间（要注意因为是整数，所以 [x,y] 与 [y+1,z] 可以合并）。 最后把合并完的区间全部输出即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define of(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int inf=1<<15;
struct node{
    int le,ri;
};
bool cmp(node a,node b){return a.le<b.le;}
vector<node> res,ans;
int main(){
    int wrong_cnt=0;//记录有多少个左端点大于右端点的区间
    while(1){
        string xxx,op;int num;
        cin>>xxx>>op>>num;
        int le=-inf,ri=inf-1;
        if(op=="<=")ri=num;
        else le=num;//记录第一个端点
        if(!(cin>>xxx)){res.push_back({le,ri});break;}
        if(xxx=="&&"){
            cin>>xxx>>op>>num;
            ri=num;//题目保证第二个条件一定是右端点
            if(le>ri)wrong_cnt++;
            if(!(cin>>xxx)){res.push_back({le,ri});break;}
        }
        res.push_back({le,ri});//记录区间
    }
    if(wrong_cnt==res.size()){cout<<"false";return 0;}//如果所有区间都是非法的，输出false
    sort(res.begin(),res.end(),cmp);
    int le=res[0].le,ri=res[0].ri;
    fo(i,1,res.size()-1){
        if(res[i].le>res[i].ri)continue;
        if(res[i].le>ri+1){
            ans.push_back({le,ri});
            le=res[i].le,ri=res[i].ri;
            continue;
        }
        ri=max(ri,res[i].ri);
    }
    ans.push_back({le,ri});//排序并合并区间
    if(ans[0].le==-inf&&ans[0].ri==inf-1){cout<<"true";return 0;}//如果区间覆盖了[-32768,32767]输出false
    fo(i,0,ans.size()-1){
        if(ans[i].ri==inf-1)cout<<"x >= "<<ans[i].le;
        else if(ans[i].le==-inf)cout<<"x <= "<<ans[i].ri;
        else cout<<"x >= "<<ans[i].le<<" && x <= "<<ans[i].ri;
        if(i!=ans.size()-1)cout<<" ||";
        cout<<endl;
    }//输出
    return 0;
}