当前位置: 首页> 教育> 高考 > 广州红盾信息门户网站_免费咨询法律_google搜索引擎官网_西安百度seo推广电话

广州红盾信息门户网站_免费咨询法律_google搜索引擎官网_西安百度seo推广电话

时间:2025/7/14 11:16:14来源:https://blog.csdn.net/x1653673086/article/details/142744992 浏览次数:0次
广州红盾信息门户网站_免费咨询法律_google搜索引擎官网_西安百度seo推广电话

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";
}
关键字:广州红盾信息门户网站_免费咨询法律_google搜索引擎官网_西安百度seo推广电话

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: