牛客练习赛132B题题解 | #江#

B题

考虑到原来的牌中重复的对最长顺子无意义,因此先去重

手牌可以视为由一段段连续的牌组成, 即一系列

使用滑动窗口遍历b数组, 不断使用鬼牌填补两段区间的空隙, 如果超出了k,则收缩左指针。

对一段使用了g张鬼牌填补的区间, 由其扩展的(不考虑其他区间)最大可能顺子长度为min(r - l + 1 + k - g, n)

例如 , 现有区间 , 已经使用了张鬼牌,在不考虑其他区间的情况下最大长度为15-10+1+5-2=9

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> PLL;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}

void print(ll x){pt(x), puts("");}

int main() {
    ll n, m, k;
    n = read();
    m = read();
    k = read();
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        a[i] = read();
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    vector<PLL> b;
    ll l = 0;
    for(ll r=1;r<a.size();r++){
        if ((a[r]-a[r-1])!=1){
            b.push_back({a[l], a[r-1]});
            l = r;
        }
    }
    b.push_back({a[l], a[n-1]});
    if (b.size()==1){
        print(min(b[0].second - b[0].first + 1 + k, m));
    }
    else{
        ll current_width = b[0].second - b[0].first + 1;
        ll ans = min(current_width + k, m);
        ll l=0;
        ll g_num = 0;
        for(ll r=1;r<b.size();r++){
            g_num += b[r].first - b[r-1].second - 1;
            while(g_num > k&&l<=r){
                g_num -= b[l+1].first - b[l].second - 1;
                l++;
            }
            ans = max(ans, min(b[r].second - b[l].first + 1 + k - g_num, m));
        }
        print(ans);
    }
    
    
    return 0;
}
全部评论

相关推荐

黑皮白袜臭脚体育生:简历统一按使用了什么技术实现了什么功能解决了什么问题或提升了什么性能指标来写会更好
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务