[UOI 2021] 第 k 小的数の题解

:::epigraph[——FFTotoro] 原题：【UR #4】元旦激光炮

这个题应该算是一个很老的交互试机题了。在 U 群里一问发现是 2015 年的题。

所以 UOI 偷偷搬运 UOJ。 :::

题意

就是有三个长 $10^6$ 的不降数组，最多查询 $65$ 次求出第 $k$ 大。

还是写个部分分吧。

分析

以下皆在大脑神经网络最小割为 $0$ 时写的，若有错误，欢迎指出。

:::info[$6 pts$] 不知道 $Q=150$ 是干什么的，问 $3k$ 次直接找就行了。 :::

:::info[$6+4=10 pts$] 不知道 $Q=150$ 是干什么的，问 $\lceil\log_2k\rceil$ 次直接找就行了。 :::

:::info[$6+4+9+13+13=45 pts$] 这样只有两个数组了，渣渣 k 给出了一个神秘做法。

还是先截掉下标大于 $k$ 的数，肯定不会贡献。

我们去问 $a_{\lfloor\frac{k}{2}\rfloor},b_{\lceil\frac{k}{2}\rceil}$，记 $i=\lfloor\frac{k}{2}\rfloor,j=\lceil\frac{k}{2}\rceil$。

如果 $a_i<b_j$，那么说明至少有 $n-j+1$ 个数不比 $a_i$ 小，至少有 $i$ 个数不比 $b_j$ 大，这样至少可以砍掉一半的数，反之亦然。

所以要问 $2\lceil\log_2k\rceil$ 次。 :::

:::info[$6+4+9+10+13+13+17+21=93 pts$] 还是 vfleaking 的做法，先往数组后补 $10^9$。

设 $l=\lfloor\frac{k}{3}\rfloor$，询问并比较 $a_l,b_l,c_l$。

设 $d_l$ 是最小的，则不大于 $d_l$ 的数至多有 $3l-3$ 个数比 $d_l$ 小，所以 $d_l$ 的排名至多是 $3l-3+1<k$。

直接砍掉 $d$ 的前 $l$ 个数，然后 $k\gets k-l$，递归到子问题。

所以要问 $\lceil\log_{3/2}k\rceil+4\approx115>65$ 次。 :::

::::info[$6+4+9+10+13+13+17+21+7=100 pts$] 扩展 $6+4+9+13+13=45 pts$ 的做法。

给每个数组设一个 $l,r$，初始时 $l=1,r=\min(len,k)$。

然后每个数组每次问 $m=\lfloor\frac{l+r}{2}\rfloor$，我们看 $m_a+m_b+m_c$ 和 $k$ 的关系。

• 如果 $m_a+m_b+m_c<k$，我们设 $d_{m_d}$ 是最小的，则它的排名小于 $k$，$l_d\gets m_d+1$；
• 设 $d_{m_d}$ 是最大的，则它的排名大于等于 $k$，$r_d\gets m_d-1$，同时更新答案。

当然边界调起来会死人，如果上述 $\gets m_d\pm1$ 更新中导致 $l>r$，就像标准二分记录下最后一次的 $m$，它有可能是第 $k$ 大，保留并不再更新 $m_d$。

说起来累死人了还是看代码吧，询问次数 $3\lceil\log_2n\rceil$，因为每个数组都要跑到 $l>r$。

:::info[Code] 注意上述保留并不再更新，所以要更新能更新的。

你就当我在上面在放屁吧，我也不知道在讲啥，还是代码简短可爱小清新易懂。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const int N = 1e6 + 10;
const int INF = 1e9;
const int MOD = 998244353;
using it2 = array<int, 2>;

int k, g;
int len[3], l[3], r[3], m[3], lst[3];

int ask(int i, int x)
{
    static int mp[3][N];
    if (x < 1)
    {
        return 0;
    }
    if (x > len[i])
    {
        return INF + 1;
    }
    if (mp[i][x])
    {
        return mp[i][x];
    }
    cout << "1 " << i + 1 << ' ' << x << endl;
    int &res = mp[i][x];
    cin >> res;
    if (~res)
    {
        return res;
    }
    else
    {
        assert(0);
    }
}

template <typename Tp>
void sort(Tp &a, Tp &b, Tp &c)
{
    if (a > b)
    {
        swap(a, b);
    }
    if (b > c)
    {
        swap(b, c);
    }
    if (a > b)
    {
        swap(a, b);
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false), cout.setf(ios::fixed), cout.precision(10);

    cin >> len[0] >> len[1] >> len[2] >> k >> g;
    l[0] = l[1] = l[2] = 1;
    r[0] = min(len[0], k), r[1] = min(len[1], k), r[2] = min(len[2], k);
    int ans = INF;
    while (l[0] <= r[0] || l[1] <= r[1] || l[2] <= r[2])
    {
        for (int i : {0, 1, 2})
        {
            if (l[i] <= r[i])
            {
                m[i] = (l[i] + r[i]) / 2;
            }
            else
            {
                m[i] = lst[i];
            }
        }
        int sum = m[0] + m[1] + m[2];
        it2 rs[3];
        for (int i : {0, 1, 2})
        {
            rs[i] = {ask(i, m[i]), i};
        }
        sort(rs[0], rs[1], rs[2]);
        if (sum >= k)
        {
            ans = min(ans, rs[2][0]);
            for (int _ : {2, 1, 0})
            {
                int i = rs[_][1];
                if (l[i] <= r[i])
                {
                    r[i] = m[i] - 1;
                    break;
                }
            }
        }
        else
        {
            for (int _ : {0, 1, 2})
            {
                int i = rs[_][1];
                if (l[i] <= r[i])
                {
                    lst[i] = m[i];
                    l[i] = m[i] + 1;
                    break;
                }
            }
        }
    }
    cout << "2 " << ans << endl;

    return 0;
}
/*
2 5 5
2 6 6
6 7 10

*/

::: ::::

代码

被我咕了，自己找。

修改于 2025/12/20：修复了一个 typo。