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++ ,