Max and Mex

题目🔗Problem - B - Codeforces
暴力写会TLE

我们分析一下数据的特点，a为max值，b为mex值，t为增加的值

   b值的大小有两种情况，要么大于a  要么小于a，不可能相等

当大于a时（b=a+1），t 的值一定为 a+1/或者b

当小于a时，t 的值小于a

        我们还可以对 t 的值讨论

AC代码（不是最优代码，但是时好代码）

#include<bits/stdc++.h>
using namespace std;
int mx=0,ln=0,ans=0;
map<int,int>mp;
int bit(int a)
{for(int i=a;i<=1000000001;i++)if(mp[i]==0)	return i;
}
int main()
{ios::sync_with_stdio(false);int T;cin>>T;while(T--){mp.clear();ans=0;mx=0;ln=0;int m,n,x;cin>>m>>n;for(int i=1;i<=m;i++){cin>>x;if(x==ln)	ln++;if(mp[x]==0)	ans++;mp[x]++;if(mx<x)	mx=x;}while(n--){ln=bit(ln);if(mx<ln){ans=ans+n+1;break;}	else if(mx>ln){int t=(ln+mx+1)/2;if(mp[t]>=1){break;}else{ans++;mp[t]++;}}}cout<<ans<<'\n';}return 0;
}

Max and Mex

题目🔗Problem - B - Codeforces
暴力写会TLE

我们分析一下数据的特点，a为max值，b为mex值，t为增加的值

   b值的大小有两种情况，要么大于a  要么小于a，不可能相等

当大于a时（b=a+1），t 的值一定为 a+1/或者b

当小于a时，t 的值小于a

        我们还可以对 t 的值讨论

AC代码（不是最优代码，但是时好代码）

#include<bits/stdc++.h>
using namespace std;
int mx=0,ln=0,ans=0;
map<int,int>mp;
int bit(int a)
{for(int i=a;i<=1000000001;i++)if(mp[i]==0)	return i;
}
int main()
{ios::sync_with_stdio(false);int T;cin>>T;while(T--){mp.clear();ans=0;mx=0;ln=0;int m,n,x;cin>>m>>n;for(int i=1;i<=m;i++){cin>>x;if(x==ln)	ln++;if(mp[x]==0)	ans++;mp[x]++;if(mx<x)	mx=x;}while(n--){ln=bit(ln);if(mx<ln){ans=ans+n+1;break;}	else if(mx>ln){int t=(ln+mx+1)/2;if(mp[t]>=1){break;}else{ans++;mp[t]++;}}}cout<<ans<<'\n';}return 0;
}