P9497 题解

rabbitohh · 2023-08-09 15:54:25 · 题解

由于每一行都是可以任意排列的，我们可以做到把每一个 >v 的数都放在不同的列（在数量 <=n）的情况下。所以我们只在每一次询问时输出矩阵中 >v 的的数的个数与 n 取 \operatorname{min} 的结果即可。如果要暴力查找的话肯定要超时，用前缀桶来存的话又存不下，因此我们用一个一维数组存下矩阵中所有数，排好序后每次询问二分即可。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int a[N];
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[(i-1)*n+j];
        }
    }
    sort(a+1,a+n*n+1);
    for(int i=1;i<=q;i++)
    {
        int v;
        cin>>v;
        int x=n*n-(lower_bound(a+1,a+n*n+1,v)-a)+1;
        cout<<min(n,x)<<'\n';
    }
    return 0;
}