POJ第3320杰西卡有毛病,考察双指针和队列
  • 板块灌水区
  • 楼主holy
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/1/19 07:56
  • 上次更新2023/10/24 03:39:24
查看原帖
POJ第3320杰西卡有毛病,考察双指针和队列
245579
holy楼主2023/1/19 07:56

3个小时没做出来,救

  1. 我的源码
  2. 题目地址
  3. 讨论区的6组测试数据 + 题目测试数据 + 自己编的5组测试数据,全部能过,提交就Runtime Error
  4. 也就是求,所有数字都包括在队列中的最小连续页数,或者说最短区间
  5. Runtime Error是为什么,数组没超限 按照讨论区指示,没用cin(会超时),没用STL库(会超时),还是不行
  6. 考察的是尺取法(双指针)
#include<iostream>
#include<cstdio> //scanf(), printf()
#include<cstring> //memset()
const int N = 1000100;
int a[N], b[N];
int main()
{
    int n, num = 0, cnt = 0, ans = N;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        if(b[a[i]] == 0) {
            num++;
            b[a[i]] = 1;
        } //得到不重复元素个数num
    }
    memset(b, 0, sizeof(b)); //初始化数组b
    for(int i = 0, j = 0; i < n; ++i) {
        if(b[a[i]] == 0) //a[i]原来不在区间内
            cnt += 1; //区间内不重复元素个数
        b[a[i]]++; //区间内a[i]个数
        while(cnt == num) { //区间包括所有内容,这里不用if
            if(ans > i - j + 1) ans = i - j + 1;
            b[a[j]]--;
            if(b[a[j]] == 0) cnt--;
            j++; //左边界右移, j++记得放最后!!!
        }
    }
    printf("%d", ans);
    return 0;
}

2023/1/19 07:56
加载中...