牛客练习赛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;
}