数组

循环控制

#include <bits/stdc++.h>
using namespace std;
int n, q, x;
int a[1123456];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1); //此时 a[n+1] 就是 0
    while (q--)
    {
        cin >> x;
        int l = 1;
        int r = n;
        int ans = n + 1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (a[mid] >= x)
            {
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        cout << a[ans] << "\n";
    }
    return 0;
}

递归控制

#include <bits/stdc++.h>
using namespace std;
int n, q, x;
int a[1123456];
//返回有序的 a[l]~a[r] 的第一个大于等于 x 的位置
int f(int l, int r, int x)
{
    if (l > r)
        return r + 1;
    if (l == r)
    {
        if (a[r] >= x)
            return r;
        else
            return r + 1;
    }
    int mid = (l + r) / 2;
    if (a[mid] >= x)
        return f(l, mid - 1, x);
    return f(mid + 1, r, x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1); //此时 a[n+1] 就是 0
    while (q--)
    {
        cin >> x;
        cout << a[f(1, n, x)] << "\n";
    }
    return 0;
}

STL：lower_bound

lower_bound：查找不到时会返回最后一个元素的后一个位置

#include <bits/stdc++.h>
using namespace std;
int n, q, x;
int a[1123456];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1); //此时 a[n+1] 就是 0
    while (q--)
    {
        cin >> x;
        int pos = lower_bound(a + 1, a + n + 1, x) - a;
        cout << a[pos] << "\n";
        // 也可以用一句：
        // cout << (*lower_bound(a + 1, a + n + 1, x)) << "\n";
    }
    return 0;
}

vector

迭代器相减得到下标

#include <bits/stdc++.h>
using namespace std;
int n, q, x, temp;
vector<int> a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> temp;
        a.push_back(temp);
    }
    sort(a.begin(), a.end());
    while (q--)
    {
        cin >> x;
        int pos = lower_bound(a.begin(), a.end(), x) - a.begin();
        if (pos == n)
            cout << 0 << "\n";
        else
            cout << a[pos] << "\n";
    }
    return 0;
}

直接用迭代器

#include <bits/stdc++.h>
using namespace std;
int n, q, x, temp;
vector<int> a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> temp;
        a.push_back(temp);
    }
    sort(a.begin(), a.end());
    while (q--)
    {
        cin >> x;
        vector<int>::iterator it = lower_bound(a.begin(), a.end(), x);
        if (it == a.end())
            cout << 0 << "\n";
        else
            cout << (*it) << "\n";
    }
    return 0;
}

set

注意！set 会自动去重，所以如果要依赖数量会有一定问题

注意！lower_bound(s.begin(), s.end(), x) 与 s.lower_bound(x) 不同！前者时间复杂度多一个 $\log$

set 每次插入的 $\log N$ 常数略大，所以初始会慢一点。

#include <bits/stdc++.h>
using namespace std;
int n, q, x, temp;
set<int> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> temp;
        s.insert(temp);
    }
    while (q--)
    {
        cin >> x;
        set<int>::iterator it = s.lower_bound(x);
        if (it == s.end())
            cout << 0 << "\n";
        else
            cout << (*it) << "\n";
    }
    return 0;
}