【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2 B题 题解

· · 题解

前言

这是我第一次自己完成洛谷月赛的 Div.2B。

但因为这天下午我在和小伙伴下棋，没能按时参与月赛。

题意

给定一个 n 行 n 列 的矩阵 a。

有 q 组询问，每次给定一个 v，请将矩阵每一行任意重排（可以不重排），最大化最大值不小于 v（也就是说，至少有一个不小于 v 的数）的列数。请输出这个列数。

询问之间相互独立。换言之，每次询问前可以重新排列。

思路

Subtask 1:

枚举重排的所有情况，时间复杂度 O(qn!^{n})。

Subtask 2:

首先发现一个性质：既然矩阵可以重排，则最好要把大的数放在不同的列中。

然后，我们可以发现：一个数无论在哪一行，都可以被放在任何一列。

我们可以将 a 数组里的数从大到小排序（我是从小到大排序的，这样做很麻烦）。

然后，顺序枚举 a 数组中的每一个数。计算有多少个数 \ge v。

但是，\ge v 的数的数量可能会 \ge n，此时，肯定有多个 \ge v 的数被放在了同一列。此时直接输出 n 即可。

时间复杂度 O(nq)。

其实，即使不排序也能过。时间复杂度 O(n^{2}q)。

Subtask 3:

实现得较好、常数较小的 O(nq) 算法已经可以过了。

但我们排了序的，又可以怎样优化呢？二分！

此外，我们可以先判断 \ge v 的数的数量是否 \ge n，以及 \ge v 的数的数量是否 =0。

然后我们在前 n 大的数中二分即可。

时间复杂度 O(q log n)。

代码

我就是从小到大排序的，这样做很麻烦（前面已经说过了）。

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n;
int q;
int cnt;
int a[N];
void solve(int v){
    int l=n*(n-1)+1;
    int r=n*n;
    if(v<=a[l]){
        printf("%d\n",n);
        return;
    }
    if(v>a[r]){
        printf("0\n");
        return;
    }
    int mid=l+r>>1;
    while(l<r){
        if(v<=a[mid])   r=mid;
        else    l=mid+1;
        mid=l+r>>1;
    }
    printf("%d\n",n*n+1-l);
    return;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int num;
            scanf("%d",&num);
            a[++cnt]=num;
        }
    }
    sort(a+1,a+cnt+1);
    while(q--){
        int v;
        scanf("%d",&v);
        solve(v);
    }
}