P6069 题解
liangbowen
·
·
题解
前言
题目传送门！
更好的阅读体验？
恶心的二分答案。（以前觉得很难，现在看来也还好？毕竟是黄题。）
思路
首先，很容易想到二分答案：\operatorname{chk(x)} 表示去掉 x 个数是否能成立。那么 \operatorname{chk(x)} 很显然具有单调性。
为了方便叙述，设和为 \texttt{sum}，平方和为 \texttt{sqsum}。
\because S=\dfrac{1}{n} \sum\limits_{i=1}^n(a_i-p)^2
\therefore S = \dfrac{1}{n} \cdot \texttt{sqsum} - \dfrac{\texttt{sum}^2}{n^2}
\therefore S = \dfrac{1}{n} \cdot (\texttt{sqsum} - \dfrac{\texttt{sum}^2}{n})
又因为我们需要 S \le \dfrac{m}{n}：
\therefore \dfrac{1}{n} \cdot (\texttt{sqsum} - \dfrac{\texttt{sum}^2}{n}) \le \dfrac{m}{n}
\therefore \texttt{sqsum} - \dfrac{\texttt{sum}^2}{n} \le m
\therefore (n \cdot \texttt{sqsum} - \texttt{sum}^2) \le n\cdot m
推这一大坨公式有什么用呢？很容易想到，要修改就修改到计算答案时没有影响，也就是可以理解为：直接去掉这个数。
还有一个很重要的结论：剩下的数最好是连续的。
感性理解，方差是衡量一组数据波动程度的指标。所以数据越接近，方差就越小。
那么有了以上的理论支持后，这道题就很水了。
预处理前缀和以及前缀平方和，然后二分，时间复杂度 O(\log n)。
所以，总时间复杂度显然就是 $O(n \log n)$，可以通过。
线性做法可以将二分改为尺取维护。排序用桶排即可。这样就能实现 $O(n)$ 了。
但是毕竟是我很久以前打的题目，就懒得写双指针了。
## 完整代码
很久以前的代码，凑合着看。
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL __int128 //直接用神器！
using namespace std;
const int N = 2e5 + 5;
int n, a[N];
long long M;
LL m, sum[N], sqsum[N];
bool chk(int peo)
{
for (int l = 1, r = peo; r <= n; l++, r++) //枚举一段长度为 peo 的区间
{
LL t1 = peo * (sqsum[r] - sqsum[l-1]); //这里就是上面推出来的公式，公式里的 n 就是 peo。
LL t2 = sum[r] - sum[l-1]; t2 *= t2;
if (t1 - t2 <= peo * m) return true;
}
return false;
}
int FIND(int l, int r) //非常模版的二分答案
{
int pos = -1; //pos 就是去掉多少个人
while (l <= r)
{
int mid = l + r >> 1;
if (chk(mid)) l = mid+1, pos = mid;
else r = mid-1;
}
return n - pos; //要求的是剩下多少人
}
int main()
{
scanf("%d%lld", &n, &M);
m = (LL)M; //懒得写快读了，这里是强转 __int128
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a+1, a+n+1); //注意要排序
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i-1] + a[i];
sqsum[i] = sqsum[i-1] + (LL)a[i] * a[i];
}
printf("%d", FIND(0, n));
return 0;
}
```
希望能帮助到大家！