51Nod 1272 最大距离

Problem

给出一个长度为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。

Solution

二分距离，后缀最大值优化检验。

Code

#include<stdio.h>
#include<set>
//#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>

#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
//using namespace std;
int n,a[50020],ans;
int mx[50020];
bool check(int x){
    //printf("%d\n",x);
    for(int i=1;i+x<=n;i++){
        if(a[i]<=mx[i+x]){
            //printf("%d %d\n",i,i+x);
            return true;
        }
    }
    return false;
}
int max(int x,int y){
    return x>y?x:y;
}
int main() {
    //io_opt;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=n;i>=1;i--){
        mx[i]=max(mx[i+1],a[i]);
    }
    int l=0,r=n-1,mid;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }
        else{
            r=mid-1;
        }
    }
    printf("%d\n",ans);
    return 0;
}