加减时间限制1 秒空间限制256M题目描述小红拿到了一个长度为nnn的数组。她每次操作可以让某个数加111或者某个数减111。小红最多能进行kkk次操作。她希望操作结束后该数组出现次数最多的元素次数尽可能多。你能求出这个最大的次数吗输入描述第一行两个正整数nnn和kkk第二行有nnn个正整数aia_iai1≤n≤1051 \le n \le 10^51≤n≤1051≤k≤10121 \le k \le 10^{12}1≤k≤10121≤ai≤1091 \le a_i \le 10^91≤ai≤109输出描述不超过kkk次操作之后数组中可能出现最多次数元素的次数。示例 1输入5 3 6 3 20 8 1输出2说明共333次操作如下第一个数加一。第二个数加一。第四个数减一。数组变成了7 4 20 7 17\ 4\ 20\ 7\ 1742071共有222个相同的数777。可以证明222为最优解。另外此上操作并不是唯一的操作。数据范围与提示1≤n≤1051 \le n \le 10^51≤n≤1051≤k≤10121 \le k \le 10^{12}1≤k≤10121≤ai≤1091 \le a_i \le 10^91≤ai≤109解题思路本题是排序 滑动窗口 中位数贪心的经典问题。给定一个长度为nnn的数组最多进行kkk次操作每次可以让某个数加 1 或减 1。目标是让操作后数组中某个元素出现的次数尽可能多求这个最大次数。1. 问题等价转化要让某个值出现的次数最多相当于从数组中选出一个连续子数组排序后通过加减操作将它们全部变成同一个数。为了使操作次数最少这个目标数应该选为该子数组的中位数因为中位数到所有点的距离之和最小。将数组升序排序后问题转化为在排序后的数组中找到一个最长的连续子数组使得将该子数组内所有元素变为其中位数所需的总操作次数不超过kkk。由于操作次数与子数组的长度和元素分布有关且对于固定右端点左端点越靠左操作次数越大满足单调性因此可以使用滑动窗口维护一个合法的区间。2. 算法实现滑动窗口 中位数维护代码使用双指针维护窗口[l,r][l, r][l,r]并实时计算将窗口内元素变为中位数所需的操作次数cur。排序将数组升序排序。初始化l 0cur 0res 0。遍历右端点r将窗口扩展到r新增元素a[r]。窗口的中位数位置为mid (l r) / 2。将a[r]变为中位数a[mid]的代价为a[r] - a[mid]累加到cur中。当cur k时需要收缩左端点移除左端点l的贡献。移除后窗口的中位数位置可能变为(l r 1) / 2。将a[l]变为新中位数的代价为a[新中位数] - a[l]从cur中减去。l。更新答案res max(res, r - l 1)。输出最终的res即为最大出现次数。3. 复杂度分析时间复杂度排序O(nlogn)O(n \log n)O(nlogn)滑动窗口过程中每个元素最多被加入和移出窗口一次每次操作O(1)O(1)O(1)总O(n)O(n)O(n)。整体O(nlogn)O(n \log n)O(nlogn)。n≤105n \le 10^5n≤105完全可行。空间复杂度需要存储数组O(n)O(n)O(n)。总结通过排序将问题转化为连续子数组的中位数调整问题利用滑动窗口在O(n)O(n)O(n)时间内找到最长合法子数组。中位数的选择保证了调整代价最小而窗口的单调性保证了双指针的正确性。该方法高效且易于实现是处理此类“通过加减操作使元素集中”问题的标准思路。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,k;vectorlla;voidsolve(){cinnk;a.resize(n);for(autox:a)cinx;sort(a.begin(),a.end());ll cur0;ll l0;ll res0;for(ll r0;rn;r){cura[r]-a[(rl)/2];while(curk){cur-a[(rl1)/2]-a[l];l;}resmax(res,r-l1);}coutres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}
加减时间限制1 秒空间限制256M题目描述小红拿到了一个长度为nnn的数组。她每次操作可以让某个数加111或者某个数减111。小红最多能进行kkk次操作。她希望操作结束后该数组出现次数最多的元素次数尽可能多。你能求出这个最大的次数吗输入描述第一行两个正整数nnn和kkk第二行有nnn个正整数aia_iai1≤n≤1051 \le n \le 10^51≤n≤1051≤k≤10121 \le k \le 10^{12}1≤k≤10121≤ai≤1091 \le a_i \le 10^91≤ai≤109输出描述不超过kkk次操作之后数组中可能出现最多次数元素的次数。示例 1输入5 3 6 3 20 8 1输出2说明共333次操作如下第一个数加一。第二个数加一。第四个数减一。数组变成了7 4 20 7 17\ 4\ 20\ 7\ 1742071共有222个相同的数777。可以证明222为最优解。另外此上操作并不是唯一的操作。数据范围与提示1≤n≤1051 \le n \le 10^51≤n≤1051≤k≤10121 \le k \le 10^{12}1≤k≤10121≤ai≤1091 \le a_i \le 10^91≤ai≤109解题思路本题是排序 滑动窗口 中位数贪心的经典问题。给定一个长度为nnn的数组最多进行kkk次操作每次可以让某个数加 1 或减 1。目标是让操作后数组中某个元素出现的次数尽可能多求这个最大次数。1. 问题等价转化要让某个值出现的次数最多相当于从数组中选出一个连续子数组排序后通过加减操作将它们全部变成同一个数。为了使操作次数最少这个目标数应该选为该子数组的中位数因为中位数到所有点的距离之和最小。将数组升序排序后问题转化为在排序后的数组中找到一个最长的连续子数组使得将该子数组内所有元素变为其中位数所需的总操作次数不超过kkk。由于操作次数与子数组的长度和元素分布有关且对于固定右端点左端点越靠左操作次数越大满足单调性因此可以使用滑动窗口维护一个合法的区间。2. 算法实现滑动窗口 中位数维护代码使用双指针维护窗口[l,r][l, r][l,r]并实时计算将窗口内元素变为中位数所需的操作次数cur。排序将数组升序排序。初始化l 0cur 0res 0。遍历右端点r将窗口扩展到r新增元素a[r]。窗口的中位数位置为mid (l r) / 2。将a[r]变为中位数a[mid]的代价为a[r] - a[mid]累加到cur中。当cur k时需要收缩左端点移除左端点l的贡献。移除后窗口的中位数位置可能变为(l r 1) / 2。将a[l]变为新中位数的代价为a[新中位数] - a[l]从cur中减去。l。更新答案res max(res, r - l 1)。输出最终的res即为最大出现次数。3. 复杂度分析时间复杂度排序O(nlogn)O(n \log n)O(nlogn)滑动窗口过程中每个元素最多被加入和移出窗口一次每次操作O(1)O(1)O(1)总O(n)O(n)O(n)。整体O(nlogn)O(n \log n)O(nlogn)。n≤105n \le 10^5n≤105完全可行。空间复杂度需要存储数组O(n)O(n)O(n)。总结通过排序将问题转化为连续子数组的中位数调整问题利用滑动窗口在O(n)O(n)O(n)时间内找到最长合法子数组。中位数的选择保证了调整代价最小而窗口的单调性保证了双指针的正确性。该方法高效且易于实现是处理此类“通过加减操作使元素集中”问题的标准思路。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,k;vectorlla;voidsolve(){cinnk;a.resize(n);for(autox:a)cinx;sort(a.begin(),a.end());ll cur0;ll l0;ll res0;for(ll r0;rn;r){cura[r]-a[(rl)/2];while(curk){cur-a[(rl1)/2]-a[l];l;}resmax(res,r-l1);}coutres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
