HDU 3530-Subsequence-単調キュー

4913 ワード

単調な行列

1.タイトルの説明:
Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6671 Accepted Submission(s): 2238
Problem Description
There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

Input
There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

Output
For each test case, print the length of the subsequence on a single line.

Sample Input

 
   
     5 0 0 1 1 1 1 1 5 0 3 1 2 3 4 5

Sample Output

5 4

Source

2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU

Recommend

zhengfeng | We have carefully selected several similar problems for you: 3535 3529 3528 3527 3531

2.题意概述：

给出一个大小为n的数组a[n];

求其中最大值减最小值在[m,k]区间中的字串最长长度。

3.解题思路：

同样可以考虑在从左扫描的同时用单调栈维护当前最值，如果最值超过了就去掉队列前面的元素，至于是去最大值还是最小值应该贪心地去掉下标最小的那个元素。

去除得到合法解，如果区间值符合，就更新一下最值，注意初始化ans应该是0！

4.AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define maxn 100100
#define lson root << 1
#define rson root << 1 | 1
#define lent (t[root].r - t[root].l + 1)
#define lenl (t[lson].r - t[lson].l + 1)
#define lenr (t[rson].r - t[rson].l + 1)
#define N 1111
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
int a[maxn], qmin[maxn], qmax[maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
#endif
    int n, m, k;
    while (~scanf("%d%d%d", &n, &m, &k))
    {
        int ans = 0, head1 = 0, head2 = 0, tail1 = 0, tail2 = 0, pre = 0;
        a[0] = qmax[0] = qmin[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            //      
            while (head1 <= tail1 && a[qmin[tail1]] > a[i])
                tail1--;
            //      
            while (head2 <= tail2 && a[qmax[tail2]] < a[i])
                tail2--;
            qmin[++tail1] = i;
            qmax[++tail2] = i;
            while (a[qmax[head2]] - a[qmin[head1]] > k)
                pre = qmin[head1] < qmax[head2] ? qmin[head1++] : qmax[head2++];
            if (a[qmax[head2]] - a[qmin[head1]] >= m && a[qmax[head2]] - a[qmin[head1]] <= k)
                ans = max(ans, i - pre);
        }
        printf("%d
", ans);
    }
#ifndef ONLINE_JUDGE
    long _end_time = clock();
    printf("time = %ld ms.", _end_time - _begin_time);
#endif
    return 0;
}

TLS/SSLを使用してHTTPエージェントを暗号化

UbuntuでのC言語によるファイルコピー機能