当前位置:编程学习 > C/C++ >>

Poj 2452 Sticks Problem (数据结构_RMQ)

题目大意: 给定一个长度为n的序列,序列里的元素都不相同,要求找出一对(i,j),i<j,arr[k]>=i&arr[k]<=j,All(i < k < j).然后求最大的j-i差值。

解题思路:RMQ+二分,有人暴力过,估计是数据的问题。先初始化rmq,这里的dp数组存储的是序列的下标。然后枚举每个结束点x,用rmq查询离x点最远的点j,使得max[j,x-1] < x,这里要用到二分,查询区间最值有rmq。找出最远的那个点j后,就要找[j,x-1]区间内值最小的那个下标i,然后x -i就是以x结尾符合条件的最长序列。
    为什么可以二分?为什么找出离x最远的点再找区间内的最小值就是以x结尾的最长序列呢?
    首先回答第一个问题,因为我们要找的是x-1以前的某个j使得max[j,x-1] < x,要找的是区间的最值,某个区间最值小于x,那么它的子区间最值也小于x,这是显然的。那找到了一个位置符合情况,就可以保证大于这个位置的都符合情况,也就自然可以往更前面查找。
    现在来回答而第二个问题,前面已经找到那个最左边的位置j了,现在要找值最小的那个i,找到了从[i,x]内的值都大等于i,小等于x,符合情况。如果不是最小的,那么这个最小的就会跳出来大吼:你大子还不够小,自然不是合法情况。

测试数据:
4
5 4 3 6
4
6 5 4 3

C艹代码:
[cpp]
#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#define MAX 51000 
 
 
int n, m, ans, arr[MAX]; 
struct RMQ { 
 
    int mmin[MAX][20]; 
    int mmax[MAX][20]; 
    void Create(); 
    int Query(int l, int r, int kind); 
} rmq; 
 
 
inline int min(int x,int y) { 
 
    return arr[x] < arr[y] ? x : y; 

inline int max(int x,int y) { 
 
    return arr[x] > arr[y] ? x : y; 

void RMQ::Create() { 
 
    int i, j = 2, k = 0; 
    for (i = 1; i <= n; ++i) 
        mmin[i][0] = mmax[i][0] = i; 
 
 
    while (j <= n) k++,j *= 2;      //用这个而非log快了1000ms 
    for (j = 1; j <= k; ++j) 
        for (i = 1; i + (1 << j) - 1 <= n; ++i) { 
 
            mmin[i][j] = min(mmin[i][j - 1], mmin[i + (1 << (j - 1))][j - 1]); 
            mmax[i][j] = max(mmax[i][j - 1], mmax[i + (1 << (j - 1))][j - 1]); 
        } 

int RMQ::Query(int l, int r, int kind) { 
 
    int i = r - l + 1, j = 2, k = 0; 
    while (j <= i) k++,j *= 2;      //用这个而非log快了1000ms 
    if (kind == 0) 
        return min(mmin[l][k], mmin[r - (1 << k) + 1][k]); 
    else 
        return max(mmax[l][k], mmax[r - (1 << k) + 1][k]); 

int Find(int x) { 
 
    int low = 1,high = x - 1; 
    int i,mid,k = -1; 
     
     
    while (low <= high) { 
         
        mid = low + (high - low) / 2; 
        i = rmq.Query(mid,x-1,1);    //查询mid至x-1最大的那个下标 
        if (arr[i] > arr[x]) low = mid + 1; 
        else k = mid,high = mid - 1; 
    } 
 
    
    if (k == -1) return x + 1;  
    i = rmq.Query(k,x-1,0);         //如果允许有重复值,这里应该二分查找最小的那个下标 
    return i; 

 
 
int main() 

    int i, j, k; 
 
 
    while (scanf("%d", &n) != EOF) { 
 
        for (i = 1; i <= n; ++i) 
            scanf("%d", &arr[i]); 
 
 
        rmq.Create(); 
        for (ans = -1,i = n; i >= 1; --i) { 
          
            k = i - Find(i); 
            if (k > ans) ans = k; 
        } 
        printf("%d\n", ans); 
    } 


作者:woshi250hua
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,