B题意:
长为n 的数组,可以对数值中任意的一个元素 进行 任意次的+x 的操作。
问数组可能的最大的mex 是什么?
n 的范围是 2e5 ,x的范围1e9
元素的范围是1e9
1.因为n 的范围是2e5,所以最大的mex就是n 、这样的数据范围就可以开桶了,(这个很快就意识到了)
2.对于a+K*x =b 这个式子,满足 a b 关于x同余。(当时做的时候,卡在了这一个点上)
思路:
遍历 a 的数值桶,同时维护a关于x余数的数值桶。(因为有效的a的范围是2e5 所以关于 x余数的数组最多开到 2e5).
void solve()
{int n,x;cin>>n>>x;vector<int>a(n+1);for (int i=0,t;i<n;i++){cin>>t;if (t>n)continue;a[t]++;}vector<int>b(min(x,n));int ans=0;for (int i=0;i<n;i++){if (i==ans&&a[i]){ans++;a[i]--;}else {if (b[ans%x]){b[ans%x]--;ans++; }else break;}if (a[i]){b[i%x]+=a[i];a[i]=0;}}cout<<ans<<"\n";
}