首页 > 其他 > 详细

51nod 1272 最大距离

时间:2020-07-08 00:26:26      阅读:92      评论:0      收藏:0      [点我收藏+]

题目网站: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)。

输出描述

输出最大距离。

样例输入

6
5
3
6
3
4
2

样例输出

3

二、解题思路

这道题发明了一个方法(也可以用单调栈 / 单调队列来做),我自己起了个名字叫做 “ 前缀累加 ” 。
这个方法也不能叫做方法吧,但可以称之为技巧。
 
能作为这两个数中的前一个数要满足的要求:前面没有小于他的,要不然答案还可以扩大
(我们把能满足这个要求的所有数字都存到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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!