8593 最大覆盖问题

时间限制:50MS 内存限制:1000K
提交次数:193 通过次数:88

题型: 编程题语言: G++;GCC;VC

Description

输入格式

第1行是正整数n，(n<=10000)

第2行是整数序列 a1   a2   ...   an

输出格式

计算出的最大覆盖区间长度

输入样例

10

1 6 2 1 -2 3 5 2 -4 3

输出样例

提示

若依次去求出每个数的最大覆盖长度，则必须有两个嵌套的循环，时间复杂度为O(n^2)。

但此处求所有数的一个最大覆盖长度，倒没有必要每个数的最大覆盖长度都求出来。

初始时，用两个指针i和j指向串末，当ai和aj的关系满足不等式时，j不动，i往左

走，……，直到不等式不满足，记录下长度。

下一步j往左移一个，i不回退，继续上面的比较，若找到更长的覆盖长度，更新。

每循环一次要么i要么j少1；最后i=-1,j=0;共进行了2(n-1)次。所以时间复杂度为O(n)。

我的思路是dp。dp[i]表示以第i个为结尾的最大覆盖长度。然后枚举第i + 1个时，如果其abs还比a[i]小，那么dp[i + 1] = 1，就是自己一个了。否则，因为它比a[i]大了，而a[i]之前也算好了dp[i]，就是[i - dp[i] + 1， dp[i] ]这段区间是比abs(a[i])小的了，所以可以不比较这段区间，直接和i - dp[i]比较即可。然后递归下去。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn =  + ;

int a[maxn];

int dp[maxn];

void work() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; ++i) {

        scanf("%d", &a[i]);

    }

    a[] = inf;

    dp[] = ;

    for (int i = ; i <= n; ++i) {

        int t = abs(a[i]);

        if (t < a[i - ]) {

            dp[i] = ;

        } else {

            int pos = i -  - dp[i - ];

            while (t >= a[pos]) {

                pos = pos - dp[pos];

            }

            dp[i] = i - pos;

        }

    }

    int ans = ;

    for (int i = ; i <= n; ++i) {

        ans = max(ans, dp[i]);

    }

    printf("%d\n", ans);

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    work();

    return ;

}

题解是用了two pointer

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn =  + ;

int a[maxn];

int dp[maxn];

void work() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; ++i) {

        scanf("%d", &a[i]);

    }

    int ans = ;

    int R = n, L = n;

    while (L >= ) {

        while (L >=  && a[L] <= abs(a[R])) {

            --L;

        }

        ans = max(ans, R - L);

        R--;

    }

    printf("%d\n", ans);

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    work();

    return ;

}

fuck

5
1 7 2 -100000 3
ans = 4

巴特西

8593 最大覆盖问题 two pointer

8593 最大覆盖问题

Description

输入格式

输出格式

输入样例

输出样例

提示

最新文章

热门文章