CodeForces 1247B2 - TV Subscriptions (Hard Version) 【思维】

墨蓝 2023-06-15 11:03 16阅读 0赞

题目链接：[https://codeforces.com/problemset/problem/1247/B2][https_codeforces.com_problemset_problem_1247_B2]

题意：就是有k种频道，现在有一个播放频道的序列，问最少需要买多少个频道使得能够连续d天看。

思路：比较简单的题目，我们只需要每次处理长度为d的区间，初始o（n）可以得到算出来需要购买的数量，然后区间右移，把左端点去掉，加上右区间端点，就可以得到一个新的答案，然后每次取最优就可以了。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 2e5 + 10;
    const int mod = 1e9 + 7;
    int a[maxn];
    map<int, int> mp;
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            mp.clear();
            int n, k, d;
            scanf("%d%d%d", &n, &k, &d);
            for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
            int L = 2, R = d + 1, tot = 0, ans = 1e9;
            for(int i = 1; i <= d; ++i)
            {
                if(mp[a[i]] == 0) ++tot;
                mp[a[i]]++;
            }
            ans = tot;
            while(R <= n)
            {
                mp[a[L - 1]]--;
                if(mp[a[L - 1]] == 0) --tot;
                if(mp[a[R]] == 0) ++tot;
                mp[a[R]]++;
                ans = min(ans, tot);
                ++L, ++R;
            }
            printf("%d\n", ans);
        }
    
        return 0;
    }

[https_codeforces.com_problemset_problem_1247_B2]: https://codeforces.com/problemset/problem/1247/B2