洛谷P3069 [USACO13JAN]牛的阵容Cow Lineup（尺取法）

思路

考虑比较朴素的解法，枚举每个长度为\(k+1\)的区间，然后统计区间中出现次数最多的颜色。这样的话复杂度为\(O(n*k)\)的，显然不行。

观察到统计每个区间中出现次数最多的颜色中，可以只用看每种颜色在区间中出现的最后一个位置，这样的话只需要我们开个桶统计一下数量就行。

所以就类似于尺取那样，维护颜色种类不超过\(k+1\)的区间，对于每次新加进来的值令其\(cnt++\)，并且维护ans。当颜色种类超过\(k+1\)时，就减去区间前面的值，因为它们与后面的颜色不可能再连在一起了。

因为每个位置都会被指针扫到最多两次，所以复杂度是\(O(n)\)的。

直接看代码好了，注意要离散化一下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;

int n, k;

int a[N], b[N];

int cnt[N];

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> k;

    for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i] ;

    sort(b + 1, b + n + 1);

    int D = unique(b + 1, b + n + 1) - b - 1;

    for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;

    int num = 0, ans = 1;

    for(int l = 1, r = 0; r <= n;) {

        r++;

        if(cnt[a[r]]++ == 0) num++;

        while(num > k + 1) {

            cnt[a[l++]]--;

            if(!cnt[a[l - 1]]) num--;

        }

        ans = max(ans, cnt[a[r]]) ;

    }

    cout << ans;

    return 0;

}

巴特西

洛谷P3069 [USACO13JAN]牛的阵容Cow Lineup（尺取法）

思路

最新文章

热门文章