自动搬运

查看原文

来自洛谷，原作者为

	peixiaorui 我太锑了

搬运于2025-08-24 22:17:40，当前版本为作者最后更新于2023-08-16 19:42:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

题目要我们求一个不等式组的解集，并以最简洁的方式输出。我们可以抽象成有多个区间，题目要我们合并区间，若这些区间覆盖了 $[-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;
}