自动搬运

查看原文

来自洛谷，原作者为

	include13_fAKe 一路坎坷而来，或将随风而去。

搬运于2025-08-24 22:48:55，当前版本为作者最后更新于2023-08-06 09:38:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

这是我第一次自己完成洛谷月赛的 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);
	}
}