纯暴力枚举

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int a[MAXN + 5]; // a[i] 第 i 个位置后面的瓶子
int Q, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> Q;
    while (Q--)
    {
        cin >> m;
        // 找到一个位置刚好打倒m个瓶子
        int pos = 0;
        for (int i = 1; i <= n; i++)
            if (a[i] == m)
                pos = i;
        cout << pos << "\n";
    }
    return 0;
}

排序后暴力枚举

如果直接排序会丢失原始位置信息，所以用 pair 来存瓶子数量和原始位置。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
// <瓶子数量, 瓶子位置>
pair<int, int> a[MAXN + 5];
int Q, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
    cin >> Q;
    while (Q--)
    {
        cin >> m;
        // 找到一个位置刚好打倒m个瓶子
        int pos = 0;
        for (int i = 1; i <= n; i++)
            if (a[i].first == m)
                pos = a[i].second;
        cout << pos << "\n";
    }
    return 0;
}

二分优化

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
// <瓶子数量, 瓶子位置>
pair<int, int> a[MAXN + 5];
int Q, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
    cin >> Q;
    while (Q--)
    {
        cin >> m;
        // 找到一个位置刚好打倒m个瓶子
        int pos = 0;
        int l = 1;
        int r = n;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (a[mid].first < m)
                l = mid + 1;
            else if (a[mid].first > m)
                r = mid - 1;
            else // a[mid].first==m
            {
                pos = a[mid].second;
                break;
            }
        }
        cout << pos << "\n";
    }
    return 0;
}

使用 map

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, Q;
map<int, int> a;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a[x] = i; // x 出现的位置为 i
    }
    // Q 次询问
    cin >> Q;
    while (Q--)
    {
        int x;
        cin >> x;
        // 之前不存在 a[x] 的话会创建一个新的 (x,0)
        cout << a[x] << "\n";
        /*
        // 更好的写法，这样不会创建多余的位置
        if (a.find(x) != a.end())
            cout << a[x] << "\n";
        else
            cout << 0 << "\n";
        */
    }
    return 0;
}