CF14B题解

· · 题解

【题目链接】

思路：

因为数据范围 a , b \le 1000 很小，所以我们可以用一个数组来存一个数他出现的次数。

然后用两个数，储存数的 l 最小值和 r 的最大值。

依次枚举每个数，看看这个数出现的次数是否等与区间个数 n，如果是的话，就更新距离。

如果枚举完都没有一个满足条件的，输出 -1。

【AC记录】

AC code:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010 , INF = 0x3f3f3f3f;
int a[N];//存出现个数的数组
int ans = INF;//答案，因为要区最小值，所以设成很大的值
bool t = false;//判断是否输出-1 
int n , k , minl , maxr;
int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) {
        int l , r;//区间的左右端点
        cin >> l >> r;
        if (l > r) swap (l , r);//若l比r大，那么交换l，r 
        minl = min (minl , l);//左端点的最小值
        maxr = max (maxr , r);//右端点的最大值
        for (int j = l; j <= r; ++ j)
            a[j] ++;//将这个区间里的数的出现次数++
    }
    for (int i = minl; i <= maxr; ++ i) //枚举每一个数
        if (a[i] == n) {//如果他是公共点
            ans = min (ans , abs(i - k));//更新答案
            t = true;//那么他就有公共节点，不用输出-1，把他设成false 
        }
    if (!t) puts("-1");//如果他们没有公共区间，输出-1。 
    else cout << ans << endl;
    return 0;
}