题目网站:http://class.51nod.com/Challenge/Problem.html#problemId=1272
一、题目描述
给出一个长度为N的整数数组A,对于每一个数组元素,如果他后面存在大于等于该元素的数,则这两个数可以组成一对。
每个元素和自己也可以组成一对。例如:{5, 3, 6, 3, 4, 2},可以组成11对,如下(数字为下标):
(0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5)。其中(1, 4)是距离最大的一对,距离为3。
输入描述
第1行:1个数N,表示数组的长度(2 <= N <= 50000)。
第2 - N + 1行:每行1个数,对应数组元素Ai(1 <= Ai <= 10^9)。
输出描述
样例输入
样例输出
二、解题思路
这道题发明了一个方法(也可以用单调栈 / 单调队列来做),我自己起了个名字叫做 “ 前缀累加 ” 。
这个方法也不能叫做方法吧,但可以称之为技巧。
能作为这两个数中的前一个数要满足的要求:前面没有小于他的,要不然答案还可以扩大
(我们把能满足这个要求的所有数字都存到A数组里)
能作为这两个数中的后一个数要满足的要求:后面没有大于他的,要不然答案还可以扩大
(我们把能满足这个要求的所有数字都存到B数组里)
相信大家读题的时候也已经发现了,我们要找的是他后面所有比这个数大于或等于的数。
我们不能比较附近挨着的两个,我们得把所有的都比较一遍,我给大家建议的方法就是:
一边输入也可以一边找出A数组中存什么数字好,输入完了后我们可以从N-1 —> 0 在来一次循环找出B数组里的数
至于怎么找呢?
我们可以记录下A数组里上一个数的下标,把 a[这个数] 和现在这个数进行比较,如果现在这个数小于上次存的那个数
A数组里多存一个i(我往A数组里存的都是下标),上次那个数的下标变成这次的下标。
B数组同理。不解释了
这时候,A数组里肯定是降序的,B数组肯定也是降序的,这点不解释了。
现在开始讲输出:
输出照常来说我们都要把A数组里的数和B数组里的数一一进行对比才能肯定哪个就是答案
可是这里我们用了一个小技巧:
假设A数组里有3个数,B数组里有3个数,正常情况来说需要判断9次,实际上这个代码可能只需要判断5次就出结果了。
而且正常情况还会TLE(超出时间限制)
那么我们这个不同寻常的技巧是什么?
首先我们肯定得判断A数组里的数肯定是得小于B数组里的数才可以的,ans取一个最大值(ans和这次的答案)
由于A数组是降序的,如果现在这个A数组里的数是小于B数组里的数,
A数组如果再往前一点(因为前面的数肯定比现在这个数要小)判断一下,如果可以的话肯定距离更大
如果ans没有重新赋值,(也就是说A数组里的数比B数组里的数大)B数组的数要往前一点,看看前面的数可不可以
三、代码描述
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long n, a[50010], A[50010], B[50010];
long long cnt_a=1, cnt_b=1, ans, prenum, postnum;
int main(){
cin >> n;
for(int i = 0;i < n;i++){
cin >> a[i];
if(prenum == 0 || a[i] < a[A[prenum-1]]){
A[prenum++] = i;
}
}
for(int i = n-1;i >= 0;i--){
if(postnum == 0 || a[i] > a[B[postnum -1]]){
B[postnum++] = i;
}
}
long long pre_idx = 0, post_idx = postnum -1;
for(;pre_idx < prenum && post_idx >= 0;){
if(a[A[pre_idx]] <= a[B[post_idx]]){
ans = max(B[post_idx] - A[pre_idx], ans);
--post_idx;
}else{
++pre_idx;
}
}
cout << ans << endl;
return 0;
}
51nod 1272 最大距离
原文:https://www.cnblogs.com/elisa02/p/13263452.html