題目鏈接

Solution

尺取法板子,算是復習一波.
題中說最多刪除 \(k\) 種,那么其實就是找一個顏色種類最多為 \(k+1\) 的區間;
統計一下其中最多的顏色出現次數.
然后直接尺取法,然后每次對于 \(col[r]\) 進行統計,時間復雜度 \(O(n)\) .

Code

#include<bits/stdc++.h> using namespace std; const int maxn=100008;int ans; int n,k,col[maxn]; map <int,int>js;int main() {scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",&col[i]);int now=0,l=1,r=0;while(r<=n){r++;if(!js[col[r]])now++;js[col[r]]++;while(now==k+2){js[col[l]]--;if(!js[col[l]])now--;l++;}ans=max(ans,js[col[r]]);}cout<<ans<<endl; }

轉載于:https://www.cnblogs.com/Kv-Stalin/p/9702870.html

總結

以上是生活随笔為你收集整理的[USACO13JAN] Cow Lineup (单调队列,尺取法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。