UVa 12174 – Shuffle [滑动窗口]

Link

传送门

Problem

You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays the songs in that order until all songs have been played. Then it reshuffles and starts playing the list again.

You have a history of the songs that have been played. However, your record of the history of played songs is not complete, as you started recording songs at a certain point in time and a number of songs might already have been played. From this history, you want to know at how many different points in the future the next reshuffle might occur.

A potential future reshuffle position is valid if it divides the recorded history into intervals of length s (the number of songs in the playlist) with the rst and last interval possibly containing less than s songs and no interval contains a specic song more than once.

Mean

你有一个音乐播放器,一用s首歌。播放器的是随机播放的:每次随机完所有歌曲后再次随机整个列表。现在你有一个长度为n的播放历史记录。每次随机播放的s首歌曲内不会重复。让你确定下次重新随机时是在第几首,有几种可能。

Analysis

扫描每个长度为s的区间,判断区间内有没有重复数字。每次扫描太耗时,所以滑动窗口,由上一个窗口递推出下一个窗口,统计每个数字出现的次数,根据每个数的次数标记出现重复的区间。

由于窗口区间会超出起始位置和最终位置,不太好处理。所以在首尾各加入不相干的区间,便于扫描。

时间复杂度为O(n)

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 400000;
int s, n, v[maxn], cnt[maxn], no[maxn];

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        memset(cnt, 0, sizeof(cnt));
        memset(no, 0, sizeof(no));
        scanf("%d%d", &s, &n);
        for(int i = 0; i < s; ++i) {
            v[i] = 110000 + i;
            ++cnt[v[i]];
            v[i+s+n] = 220000 + i;
        }
        for(int i = 0; i < n; ++i)
            scanf("%d", &v[i+s]);
        int multi = 0;
        for(int st = 1; st < s + n; ++st) {
            int ed = st + s - 1;
            if(--cnt[v[st-1]] == 1)
                --multi;
            if(++cnt[v[ed]] == 2)
                ++multi;
            if(multi)
                no[st%s] = true;
        }
        int res = 0;
        for(int i = 0; i < s; ++i)
            if(!no[i]) ++res;
        printf("%d\n", res);
    }
    return 0;
}

欢迎留言