【贪心+双指针】阿宁睡大觉

た入场券 2024-03-16 19:49 49阅读 0赞

[E-阿宁睡大觉\_牛客小白月赛56 (nowcoder.com)][E-_56 _nowcoder.com]

题意：

![3ce50b7a2e2140bb91ede8d3206f0d1f.png][]

![d58d11e20aed4f69a795170e93f78039.png][]

思路：

首先有个很明显的结论：去掉2贡献要不变小要不不变，因此一定是去掉0

那么就是贪心，将连续0的区间长度排序，然后计算贡献

那就是很经典的while(1)型的双指针了，很重要的一点是：要去掉前缀0区间和后缀0区间，这两个区间不能算进贡献里

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=2e5+10;
    const int mod=998244353;
    
    string s;
    
    int N,K;
    int a[mxn];
    
    void solve(){
        cin>>N>>K>>s;
        s=" "+s;
        for(int i=1;i<=N;i++){
            if(s[i]=='Z') a[i]=2;
            else a[i]=0;
        }
        int ans=0ll;
        for(int i=2;i<=N;i++) ans+=a[i]*a[i-1];
        vector<int> V;
        int L=1,R=N;
        while(L<=N&&a[L]==0) L++;
        while(R>=1&&a[R]==0) R--;
        int l=L,r=L;
        while(1){
            if(l>R||r>R) break;
            while(l<=R&&a[l]==2) l++;
            r=l;
            while(r<=R&&a[r]==0) r++;
            if(l<=r-1) V.push_back(r-1-l+1);
            l=r;
        }
        sort(V.begin(),V.end());
        int res=K;
        for(int i=0;i<V.size();i++){
            if(res>=V[i]){
                res-=V[i];
                ans+=4;
            }else break;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

除了while(1)型的双指针，还有另一种写法：

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define ull unsigned long long
    #define F(i, a, b) for (int i = a; i <= (b); ++i)
    #define dF(i, a, b) for (int i = a; i >= (b); --i)
    const int N = 1e5 + 7;
    const int mod = 998244353;
    void solve(){
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<int> w(n + 1);
        int ans = 0;
        F(i,0,n-1){
            w[i + 1] = s[i] == 'z' ? 0 : 2;
        }
        F(i, 1, n - 1) ans += w[i] * w[i + 1];
        int l = 1;
        while(l<=n&&w[l]==0) l++;
        int L = 0;
        vector<int> v;
        F(i,l,n){
            if(w[i]==2){
                if(!L) continue;
                v.push_back(i - L);
                L = 0;
            }
            else{
                if(!L) L = i;
            }
        }
        sort(v.begin(), v.end());
        for(auto len:v){
            if(k>=len)
                k -= len, ans += 4;
            else 
                break;
        }
        cout << ans << "\n";
    } 
    int main(){
        // freopen("C:\\Users\\86155\\Desktop\\1.in","r",stdin);freopen("C:\\Users\\86155\\Desktop\\1.out","w",stdout);
        ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        int t = 1;
        while(t--){
            solve();
        }
        return 0;
    }

[E-_56 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/39100/E
[3ce50b7a2e2140bb91ede8d3206f0d1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3971332e0a504b8a81a28bb87942cff2.png
[d58d11e20aed4f69a795170e93f78039.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0d41247e52c5488ea54c2a560e051a78.png