11536 - Smallest Sub - Array (슬라이딩 창)

1746 단어 ACMuva
이 문 제 는 사실 lrj 가 말 하 는 미끄럼 창의 작은 변형 이지 만 이 창의 크기 는 가 변 적 입 니 다. 구체 적 인 방법 은 예제 Shuffle 과 유사 합 니 다. 처음 과 끝 두 개의 포인터 로 창 을 유지 하고 하나의 배열 cnct 로 1 ~ k 의 모든 숫자 가 창 에 나타 난 횟수 를 기록 합 니 다. 하나의 변수 c 로 창 에 한 번 만 나타 난 숫자의 개 수 를 기록 합 니 다.  이렇게 하면 c = = k 이것 이 조건 을 만족 시 키 는 답 이 고 최소 의 답 을 취하 면 된다.
모든 요소 가 한 번 만 삽입 되 어 삭제 되 기 때문에 시간 복잡 도 는 O (n) 입 니 다.
이 알고리즘 은 길이 가 알 수 없 는 연속 구간 을 처리 하고 답 이 나 올 때 까지 구간 의 시작 과 끝 을 반복 적 으로 추진 하 는 것 이 특징 인 '취 척 법' 이라는 이름 도 있다.
자세 한 참조 코드:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 10;
int T,n,m,k,Case = 0,a[maxn],cnt[maxn];
map<int,int> p;
vector<int> g[105];
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d",&n,&m,&k);
        memset(cnt,0,sizeof(cnt));
        a[1] = 1; a[2] = 2; a[3] = 3;
        if(n>3) for(int i=4;i<=n;i++) {
            a[i] = (a[i-1]+a[i-2]+a[i-3])%m + 1;
        }
        int ans = 2000000000;
        int rear = 0,last = 1,c = 0;
        while(true) {
            if(c == k) {
                cnt[a[last]] -- ;
                if(cnt[a[last]] == 0 && a[last] <= k) c--;
                last++;
                if(c == k) ans = min(ans , rear - last + 1);
            }
            else {
                rear ++;
                if(rear > n) break;
                cnt[a[rear]]++;
                if(cnt[a[rear]] == 1 && a[rear] <= k) c++;

                if(c == k) ans = min(ans , rear - last + 1);

            }
        }
        printf("Case %d: ",++Case);
        if(ans != 2000000000) printf("%d
",ans);
        else printf("sequence nai
");
    }
    return 0;
}
AcWing 1142 바 쁜 도시
MySQL 기본 이해 (1 ')

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage