2015多校联合训练第一场Assignment（hdu5289）三种解法

本文主要是介绍2015多校联合训练第一场Assignment（hdu5289）三种解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：给出一个数列，问其中存在多少连续子序列，子序列的最大值-最小值< k
这题有三种解法：
1：单调队列,时间复杂度O(n)
2：RMQ+二分,时间复杂度O(nlogn)
3：RMQ+贪心,时间复杂度O(nlogn)

一：RMQ+二分
RMQ维护最大值，最小值，枚举左端点i，二分找出最远的符合的右端点j，答案就是ans += j - i+1;(手推一下就知道)
比如1 2 3
含有i的有三种
1
1 2
1 2 3
其它的2,2 3,3下面i=2的时候会算的，所以每次加j-i+1就行

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;int  maxsum[100000][30];
int minsum[100000][30];int a[100000];
int n,k;
void rmq_init()
{for(int j = 1; (1<<j) <= n; ++j)for(int i = 1; i + (1<<j) - 1 <= n; ++i){maxsum[i][j] = max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]); minsum[i][j] = min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);}}int query(int l, int r)
{int k = log2(r-l+1);int Max = max(maxsum[l][k], maxsum[r-(1<<k)+1][k]);int Min = min(minsum[l][k], minsum[r-(1<<k)+1][k]);return Max - Min;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);for(int i = 1; i <= n;++i){scanf("%d",a+i);maxsum[i][0] = minsum[i][0] = a[i];}rmq_init();long long  ans = 0;int l , r;for(int i = 1; i <= n; ++i){l = i , r = n;while(l <= r){int mid = (l+r)/2;int cha = query(i,mid);if(cha < k) l = mid+1;else r = mid - 1;}ans += l - i;}printf("%lld\n",ans);}return 0;
}

二:单调队列
用单调队列维护最大值最小值，双指针，第一个第二个指针初始指向第一个数据，第一个指针按顺序不断向队尾添加数据，当最大值最小值的差大于等于k后，就意味着新添加的这个不能作用于当前第二个指针的位置，也就能计算出，以第二个指针位置开始的连续子序列的个数，最后统计总和。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std ;
#define LL long long
deque <LL> Max , Min ;
//单调队列，Max最大值，Min最小值
LL a[100010] ;
int main()
{int T , n , i , j ;LL k , ans ;scanf("%d", &T) ;while( T-- ){scanf("%d %I64d", &n, &k) ;for(i = 0 ; i < n ; i++)scanf("%I64d", &a[i]) ;while( !Max.empty() ) Max.pop_back() ;while( !Min.empty() ) Min.pop_back() ;for(i = 0 , j = 0 , ans = 0; i < n ; i++)  //i在前，j在后{while( !Max.empty() && Max.back() < a[i] ) Max.pop_back() ;Max.push_back(a[i]) ;while( !Min.empty() && Min.back() > a[i] ) Min.pop_back() ;Min.push_back(a[i]) ;while( !Max.empty() && !Min.empty() && Max.front() - Min.front() >= k ){ans += (i-j) ;if( Max.front() == a[j] ) Max.pop_front() ;if( Min.front() == a[j] ) Min.pop_front() ;j++ ;}}while( j < n ){ans += (i-j) ;j++ ;}printf("%lld\n", ans) ;}return 0 ;
}

三:RMQ+贪心
这种枚举右端点，贪心选取右端点（类似尺取法）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;int  maxsum[100000][30];
int minsum[100000][30];int a[100000];
int n,m;
void rmq_init()
{for(int j = 1; (1<<j) <= n; ++j)for(int i = 1; i + (1<<j) - 1 <= n; ++i){maxsum[i][j] = max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);minsum[i][j] = min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);}}int query(int l, int r)
{int k = log2(r-l+1);int Max = max(maxsum[l][k], maxsum[r-(1<<k)+1][k]);int Min = min(minsum[l][k], minsum[r-(1<<k)+1][k]);return Max - Min;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i = 1; i <= n; ++i){scanf("%d",a+i);maxsum[i][0] = minsum[i][0] = a[i];}rmq_init();long long  ans = 0;int k=1;for(int i=1; i<=n; i++){while(query(k,i)>=m&&k<i)k++;ans+=(i-k+1);}printf("%lld\n",ans);}return 0;
}