louisfghbvc的部落格

題目大意:  超過長度K的木板，拿掉。問最大長度。

思路:  貪心，首先一個字母算連續出現幾次，超過K次，就排序把最小拿掉。用Sliding Window 概念去想。均攤O(NlogN)，長度最長N，可是如果很多分散連續字母，排序時間不會花費太多時間，

代碼:  

#include <bits/stdc++.h>

#define louisfghbvc int t; cin >> t; while(t--)
typedef long long LL;
using namespace std;

const int N = 2e5+5;
LL arr[N];

void solve(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> arr[i];
    string s;
    cin >> s;

    for(int r = 0, l = 0; r < n; ++r){
        if(r+1<n && s[r] == s[r+1]){
            // nothing
        }
        else{
            sort(arr + l, arr + r + 1, [&](int a, int b){
                    return a > b;
                 });
            l = r+1;
        }
    }

    LL sum = 0, len = 0;
    for(int i = 0; i < n; ++i){
        sum += arr[i];
        if(i && s[i] == s[i-1]){
            if(++len > k){
                sum -= arr[i];
                len--;
            }
        }
        else{
            len = 1;
        }
    }

    cout << sum << "\n";
}

int main()
{
    //louisfghbvc{
        solve();
    //}
    return 0;
}