题解：CF1920A. Satisfying Constraints

题解：CF1920A. Satisfying Constraints

• 题意简述

先给个题目链接：CF1920A。

• 做法解析

这题的洛谷评级是入门，所以不要去想什么树状数组、线段树，直接想不需要任何算法的做法。

先考虑操作①②，对于这两个操作，我们可以把k的范围缩小到l到r中间，其中l是所有操作①中x的最大值，r是所有操作②中x的最小值。

显然此时的答案是r-l+1，但如果l>r就直接输出0。

在考虑操作③，可以把每个x扔进以set，最后遍历一次整个set，如果某一个数在l~r的范围内就把答案减一（数据已经保证没有重复，set还可以去重）。

最后特殊判断一下，如果答案已经小于0就输出0，当然不加也没关系。

注意最初set要清空。

• 代码示范

#include<bits/stdc++.h>
using namespace std;
set<int>num={};
int n=0,t=0;
int main(){
    scanf("%d",&t);
    for(int h=1;h<=t;h++){
        num.clear();
        scanf("%d",&n);
        int l=1,r=1e9;
        for(int i=1;i<=n;i++){
            int opt=0,x=0;
            scanf("%d%d",&opt,&x);
            if(opt==1){
                l=max(l,x);
            }else{
                if(opt==2){
                    r=min(r,x);
                }else{
                    num.insert(x);
                }
            }
        }
        if(l>r){
            printf("0\n");
        }else{
            int ans=r-l+1;
            while(num.empty()==false){
                int now=*num.begin();
                if(l<=now&&now<=r){
                    ans--;
                }
                num.erase(num.begin());
            }
            printf("%d\n",max(ans,0));
        }
    }
    return 0;
}