CF14B Young Photographer 题解

CodeForces-CF14B
Luogu-CF14B

题目大意

这道题主要思路是模拟，也用了一点暴力的思想。

题目给出一个一维的坐标轴，并在上面选取了一个点 \(x_0\)。之后给了我们 \(n\) 个区间，要求我们找出这些区间的公共区间，输出这个子区间中对 \(x_0\) 的最短距离。

在题目翻译中可能对于公共区间的表述不是很清楚。所有区间的共同部分才是公共区间。而不是只要有公共的即可。

解决思路

对于上面公共区间的定义，我们可以清楚。只有当全部的区间都读入之后，我们才能找到公共区间。

看到数据范围，区间长度最大只有 \(1000\)，那么我们想到直接暴力开桶，用来存放坐标轴上的每个点被 \(n\) 个区间覆盖的次数。很容易得出，只有覆盖次数为 \(n\) 次时，这个点才是公共区间的一个元素。

当存到最后一个区间时，如果次数为 \(n\)，那么我们可以进行计算，不断更新最小的距离。

如果区间全部扫完，答案没有被更新，则说明没有公共区间。细节见代码部分。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;

ll n, x0, ans = 998244353; //ans记录答案
int a[1003]; //统计每个点出现的次数

int main()
{
    cin >> n >> x0; //如题目描述
    for (int i = 1; i <= n; ++i)
    {
        int l, r; //待读入区间的左端点和右端点
        cin >> l >> r; //读入区间
        if (l > r) //保证区间左边小，右边大，方便后续操作
            swap(l, r);
        for (int i = l; i <= r; ++i)
        {
            a[i]++; //累加每个点出现的次数
            if (a[i] == n) 
            /*
            当出现点的次数为 n 时，
            即此时的区间已经全部读入，
            说明这个点是公共区间的一部分。
            */
            {
                ll cha = i - x0; //计算这个点到x0的距离
                ans = min(ans, (cha >= 0 ? cha : -cha)); //更新答案
            }
        }
    }
    if (ans == 998244353) //ans的值没有被修改，说明没有公共区间
        ans = -1; //即输出 -1
    printf("%lld\n", ans); //输出答案
    return 0; //养成好习惯
}