自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:17:06，当前版本为作者最后更新于2022-09-30 17:16:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题目传送门！

更好的阅读体验？

恶心的二分答案。（以前觉得很难，现在看来也还好？毕竟是黄题。）

思路

首先，很容易想到二分答案：$\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)$。

$\operatorname{chk(x)}$ 枚举连续的区间即可，时间复杂度 $O(n)$。

所以，总时间复杂度显然就是 $O(n \log n)$，可以通过。

线性做法可以将二分改为尺取维护。排序用桶排即可。这样就能实现 $O(n)$ 了。

但是毕竟是我很久以前打的题目，就懒得写双指针了。

完整代码

很久以前的代码，凑合着看。

#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;
}

希望能帮助到大家！