P14924 [GESP202512 八级] 宝石项链贪心题解

zhangyuqi277h · 2024-12-15 11:09:18 · 题解

发现题解中竟然没有我这么蒻的思路，赶紧补发一篇（主要是滑动窗口没什么新意，主要是处理环状的思路那块）

先上核心代码

if(!f){
  n+=l;
  f=1;
}

这是什么意思呢？别急，放到整体（平平无奇）的代码中看看

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+100;
int n,m,t[N],cnt[N],dp[N],l=0,r,init=0,ps=0;
bool f=0;
struct node{
    int ls,rs;
}s[N];
bool cmp(node a,node b){
    if(a.rs!=b.rs) return a.rs<b.rs;
    else return a.ls>b.ls;
}
int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> t[i];
    }
    for(int i=n;i<=2*n;i++){
        t[i]=t[i-n];
    }
    for(int r=0;r<n;r++){
        if(cnt[t[r]]==0) init++;
        cnt[t[r]]++;
        if(init==m){
            while(cnt[t[l]]-1>0) cnt[t[l++]]--;
            s[ps++]=node{l,r+1};
            if(!f){    //在这里！！！
                n+=l;
                f=1;
            }
        }
    }
    sort(s,s+ps,cmp);
    for(int i=0;i<ps;i++){
        dp[s[i].rs]=1;
        dp[s[i].rs]+=dp[s[i].ls];
        dp[s[i].rs]=max(dp[s[i].rs-1],dp[s[i].rs]);
    }
    cout << dp[s[ps-1].rs];
    return 0;
}

它的意思就是如果你处理到第一个可以切下来的合法的部分的时候，前面有没用到的（可能前面的宝石在这一段合法的区间内肯定有，所以ta没用了）

显然你在后面（到输入的最后一个之前）也并不会用到这一段在 第一次就没用到的（因为滑动窗口左端点不会往左）所以你可以放心大胆的把这一段扔到最后去，也就是 n+=l 。

贪心选择没啥好说的，这样就几乎实现了O(n)。

AC记录