B题
大体思路
先对数据进行处理,然后枚举所有可能的开头并用二分找它的最长的结尾,最后取出最长的
数据处理
由于"顺子"特性,我们先对其进行排序并去重
//去重+排序
//用unique()将重复值移到后面去,再用erase去掉重复的值
sort(a.begin(),a.end());//必须先排序后去重:unique只消除相邻的重复值
auto it=unique(a.begin(),a.end());
a.erase(it,a.end());
我们可以把鬼牌理解为一个可以弥补空缺的东西,那么我们用前缀和算法来算出某个区间如果想有顺子需要的鬼牌数,通过这个来和我们鬼牌数对比,就可以很方便的进行检查一个区间是否可以组成顺子
bool check(int st,int en){
if(prefix[en]-prefix[st]>k) return false;
else return true;
}
枚举并二分
有了这个check的方法我们就可以实现二分
//遍历每一个可能的开头,二分查找它的末尾
for(int i=0;i<a.size();i++){
if(i>0&&a[i]-a[i-1]==1) continue;//如果连续则不能比之前的那个大,剪枝
int l=i,r=a.size()-1,mid;
while(l<r){
mid=(l+r+1)>>1;//二分用右移运算符一次表示/2
if(check(i,mid)) l=mid;
else r=mid-1;
}
//如果这个连续区间长度+剩下鬼牌数比m大就输出m
if(l-i+1+k>=m){
ml=m;
break;
}
else{
ml=ml>l-i+1+k?ml:l-i+1+k;
}
}
要注意的是,算最长的时候要把剩下的k都用掉,但是总量不能比m更大
完整代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> a;
vector<int> prefix;
long long tem;
int n;
long long ml;
long long k,m;
bool check(int st,int en){
if(prefix[en]-prefix[st]>k) return false;
else return true;
}
int main(){
scanf("%d %lld %lld",&n,&m,&k);
for(int i=0;i<n;i++){
scanf("%lld",&tem);
a.push_back(tem);
}
ml=min(k+1,m);
//去重+排序
//用unique()将重复值移到后面去,再用erase去掉重复的值
sort(a.begin(),a.end());//必须先排序后去重:unique只消除相邻的重复值
auto it=unique(a.begin(),a.end());
a.erase(it,a.end());
//前缀和求出某个区间内需要鬼牌的数量
prefix.push_back(0);
for(int i=1;i<a.size();i++){
prefix.push_back(a[i]-a[i-1]-1+prefix[i-1]);
}
//遍历每一个可能的开头,二分查找它的末尾
for(int i=0;i<a.size();i++){
if(i>0&&a[i]-a[i-1]==1) continue;//如果连续则不能比之前的那个大,剪枝
int l=i,r=a.size()-1,mid;
while(l<r){
mid=(l+r+1)>>1;//二分用右移运算符一次表示/2
if(check(i,mid)) l=mid;
else r=mid-1;
}
//如果这个连续区间长度+剩下鬼牌数比m大就输出m
if(l-i+1+k>=m){
ml=m;
break;
}
else{
ml=ml>l-i+1+k?ml:l-i+1+k;
}
}
printf("%lld",ml);
return 0;
}