BZOJ 5110 [CodePlus2017]Yazid 的新生舞会 O(n)

39 阅读 0 评论 26 点赞

我是靠谱客的博主平常鸭子，最近开发中收集的这篇文章主要介绍BZOJ 5110 [CodePlus2017]Yazid 的新生舞会 O(n)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题面
题解:
枚举每个数作为众数,枚举到的数赋为+1,其它数赋为-1.
走一次统计一次肯定不现实,考虑动态更新走到当前点的答案res.
设sum为当前前缀和,f[i]表示前缀和为i的点有f[i]个,res即为所有小于sum的f[i]的和.
若接下去有一连串-1使得sum小于最小值,则一步跳到这串-1的末尾(因为不用统计答案)
这时就需要一个差分数组cf,在起点打-1标记,在终点打+1标记,走到i时若cf[i]不为零,则用cf[i]更新f[i],同时更新cf[i+1]

整理一下每走一步要做什么
若当前位为+1:

f[sum]+=cf[sum];
cf[sum+1]+=cf[sum]
cf[sum]=0;
f[sum]++;
sum++;
res+=f[sum-1];
ans+=res;

若当前位为-1:

f[sum]++;
sum--
res-=f[sum];
ans+=res;
更新最小值

Code

最后

以上就是平常鸭子为你收集整理的BZOJ 5110 [CodePlus2017]Yazid 的新生舞会 O(n)的全部内容，希望文章能够帮你解决BZOJ 5110 [CodePlus2017]Yazid 的新生舞会 O(n)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：======算法======
浏览次数：39 次浏览
发布日期：2024-09-06 02:35:02
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_14_f2_12__7__22_4.html

BZOJ 5110 [CodePlus2017]Yazid 的新生舞会 O(n)

概述

最后

评论列表共有 0 条评论

发表评论取消回复

BZOJ 5110 [CodePlus2017]Yazid 的新生舞会 O(n)

概述

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复