AT_abc296_c [ABC296C] Gap Existence 题解

· · 题解

AT_abc296_c [ABC296C] Gap Existence 题解

题目分析

二分练习题。我们先把数组排好序，并定义一个 ans 保存答案。然后从 1 枚举到 n，然后每次在 a 数组里查找有多少个 a_i + x，并保存起止位置和终止位置。这里我用到了 \text{lower\_bound} 和 \text{upper\_bound}，不知道的可以参考这篇文章。如果起始位置 \mathrlap{\,/}{= n + 1}，就把 ans 加上终止位置减去起始位置，否则把 ans 加 0。然后遍历完之后判断 ans 是否 > 0 是则输出 Yes，否则输出 No。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 200020;
int n, c, a[N], ans = 0;

int solve(int ans)
{
    int start = lower_bound(a + 1, a + n + 1, ans) - a;
    int last = upper_bound(a + 1, a + n + 1, ans) - a;
    if (start != n + 1)
        return last - start;
    else
        return 0;
}

signed main()
{
    qwq;
    cin >> n >> c;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i)
    {
        ans += solve(a[i] + c);
    }
    if (ans > 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}