自动搬运

查看原文

来自洛谷，原作者为

	I_AM_TLEer 数学是科学的皇后，也是世界的法则。

搬运于2025-08-24 23:09:15，当前版本为作者最后更新于2025-02-13 23:49:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题评价：本题思想工作挺难的，但想好后就容易多了。

正文

相信各位都读懂题意了，在此我就不再赘述了。

定义：在网格图中，第一列第 $n$ 个数记作 $A_{n}$ 。第一行第 $n$ 个数记作 $B_{n}$ 。网格图中第 $i$ 列第 $j$ 行的格子记作 $O_{i,j}$ 。（不存在 $O_ {i,0},O_{0,j}$）。

如果只是单纯的暴力加模拟，一定会 TLE or MLE。

那么，该如何解决呢？

MLE 问题

注意到：对于任意 $O_{i,j}$ 都有 $O_{i,j}=\max(A_{1}\dots A_{i},B_{1}\dots B_{j})$。

为了简化操作 ， 我们用一种类似于前缀和的方式做预处理。 使得 $A_{i}=\max(A_{1}\dots A_{i})$ ， $B_{i}=\max(B_{1}\dots B_{i})$ 。 即：让序列 A ，序列 B 单调不降。

这样， $O_{i,j}=\max(A_{i},B_{j})$ 。 我们可以直接从预处理的序列 A ，序列 B 推出网格图中的某一格子，空间复杂度从 $O(n^{2})$ 降到了 $O(n)$ 。

TLE 问题

为了解决 MLE 问题，我们竟阴差阳错地得到了一个宝贝单调不降序列。

目前，我们每次要提出一个 $A_{i}$ 并与整个序列 B 做一轮比较。

容易发现：总有前几个数数值是相同的且等于 $A_{i}$ ，我们暂时把这个“几”记作 $xp$ 吧。

很容易明白，这是因为序列 B 单调不降。前 $xp$ 个数都小于等于 $A_{i}$ 。

可以考虑二分。这样的话，时间复杂度就会变为 $O(n\log{n})$ 了。

别忘了序列 A 也是单调不降的。

因为 $A_{i}\le A_{i+1}$ 这使得 $xp$ 也只增不减。

考虑双指针。因为两个指针只把两个序列扫一遍，因此时间复杂度变成 $O(n)$ 了。

查找，输出答案

实在想不出别的算法了，就排序吧（痛失 $O(n)$ 的时间复杂度）。

AC code：

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

#define N (int)2e5+10
int n, xp = 1;

struct num {
	int t, m;
	long long c;
}A[N], B[N], AB_h[2*N];

//-----------------------------------------------------
/*		第一部分 
N 代表 n 的上限 
n 接收 网格图的边长
xp 是 辅助变量，用于查找各个数出现的次数

结构体 num 中：
	t 记录输入的原始数据。 
	m 类似指针，在预处理时指向比它大的数或自己。 
	c 用于记录此数 (t) 出现的次数。

序列A，序列B，分别储存输入的数。
在代码的最后用 AB_h 合并序列A，序列B以便求出答案。

温馨提示： 不开 long long 见祖宗。 
*/ 

bool cmp_one (num a,num b) {
	return a.t > b.t;
}

bool cmp_two (num a,num b) {
	if (a.c == b.c)
		return a.t > b.t;
	else return a.c > b.c;
}

//-----------------------------------------------------
/*		第二部分
两次排序 cmp 均对 num 结构体。 
第一次排序：把相同数 (t) 的放在一起，方便次数相加。 
第二次排序：按照题目要求排序，查找到答案。 
*/ 

int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i ++) {
		scanf("%d", &A[i].t);
		A[i].m = i;	A[i].c = 1;
		if (i >= 2 && A[i].t < A[A[i-1].m].t)
			A[i].m = A[i-1].m;
	}
	for (int i = 0; i < n; i ++) {
		scanf("%d", &B[i].t);
		B[i].m = i;	B[i].c = 1;
		if (i >= 2 && B[i].t < B[B[i-1].m].t)
			B[i].m = B[i-1].m;
	}
	B[0].c = 0;
	
//-----------------------------------------------------
/*		第三部分-输入部分
输入序列A，序列B并初始化。同时对两者做预处理。 
特殊的东西必须特殊对待，直接把左上角的数的次数调为0
*/ 
	
	for (int i = 1; i < n; i ++) {
		while (A[A[i].m].t >= B[B[xp].m].t && xp < n){
			B[B[xp].m].c += i-1;
			xp ++;
		}
		A[A[i].m].c += xp-1;
	}
	while (xp < n) {
		B[B[xp].m].c += n-1;
		xp ++;
	}
	
//-----------------------------------------------------
/*		第四部分-处理部分1 
xp 作辅助变量，找到各个数的次数，累加到序列A，序列B中。
有个别的数据点使得 xp 不能扫到最后，因此再用 While 封个底
*/ 
	
	for (int i = 0; i < n; i ++) {
		AB_h[2*i+0].t = A[i].t; AB_h[2*i+0].c = A[i].c;
		AB_h[2*i+1].t = B[i].t; AB_h[2*i+1].c = B[i].c;
	}
	sort(AB_h, AB_h+2*n, cmp_one);
	for (int i = 2*n; i >= 0; i --) {
		if (AB_h[i].t == AB_h[i+1].t) {
			AB_h[i].c += AB_h[i+1].c;
			AB_h[i+1].t = AB_h[i+1].c = 0;
		}
	}
	
//-----------------------------------------------------
/*		第五部分-处理部分2
交错存储到AB_h中。
第一次排序后对相同数(t)的次数相加并把后者删除。 
*/ 
	
	sort(AB_h, AB_h+2*n, cmp_two);
	printf("%d %lld", AB_h[0].t, AB_h[0].c);
	
//-----------------------------------------------------
/*		第六部分-输出部分 
第二次排序 输出答案
*/ 
	
    return 0; //完结 
}

后记

时间复杂度为 $O(n\log{n})$ 。 空间复杂度为 $O(n)$ 。

AC 记录。

运行得还算快，用时 $280ms$ 。

What can I say ? I_AM_TLEer out !。