自动搬运

查看原文

来自洛谷，原作者为

	xzyg 一个不正经的正经人

搬运于2025-08-24 22:34:33，当前版本为作者最后更新于2021-11-17 22:56:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

蒟蒻的第一篇题解

题目传送门

Sol 0

暴力模拟+二分

然鹅赛后被 hack 掉了。

Sol 1

排序+后缀和

每次删数必定是从小到大删，考虑对原数组进行排序。对于需判断的一个数 $a_p$，剩余数只能大于等于 $a_p$。

可以维护一个后缀和，$O(1)$ 算出 当前 $avg-k_i$，用一个指针标记当前删数的位置，从而使每次询问优化到 $O(n)$。

复杂度 $O(qn)$，期望得分：50pts

Sol 1.5

依照上面的思路，设第 $i$ 个数及后面数的平均数为 $avg_i$，当前剩余最小数为 $a_i$。

若 $a_i$ 被 $avg_i-k$ 删掉，如果先不删它，那么它必定也会在下一轮中被 $avg_{i+1}-k$ 删掉。

若 $a_i$ 未被 $avg_i-k$ 删掉，那么即符合要求，停止删数。

可以发现，只需要将 $a_i$ 与 $avg_i-k$ 比较就能确定 $a_i$ 的删除情况。

将这个结论稍加扩展：对于排序后序列中的一个数 $a_i$，若 $a_i$ 之前的数都被删掉，那么只需要判断 $a_i$ 与 $avg_i-k$ 的大小关系，就可以确定 $a_i$ 的删除情况。

每次询问 $O(n)$ 扫一遍原数组，

复杂度 $O(qn)$，期望得分：50pts。

梅开二度

尽管在时间上并没有优化，但在算法简单了许多，只需循环上套个判断就可以了。

Sol 2

考虑对多次查询进行优化。

显然，若 $k_i > k_{i+1}$，则 $avg-k_i < avg-k_{i+1}$。限制变大，从而满足条件的数减少、答案减小，可以利用这点进行优化。

其他大佬都是用的双指针，这里介绍另一种无脑的方法：将询问数组从大到小 sort 一遍，当某个 $k$ 找到答案时，更小的 $k$ 接着往右搜，最后再按编号 sort 回来输出就可以了，这样就可以做到 $O(n)$ 处理。

复杂度：$O(n\log n+q\log q)$ 期望得分：100pts。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct xmh{		//%%%xmh
	ll val,num,ans;
}k[100010];

ll n,q;
ll a[100010];
ll add[100010];
double avg[100010];

inline bool cmp1(xmh a,xmh b){
	return a.val > b.val;
}
inline bool cmp2(xmh a,xmh b){
	return a.num < b.num;
}

void init(){
	memset(a,0,sizeof(a));						//初始化 
	memset(add,0,sizeof(add));
	memset(avg,0,sizeof(avg));
	memset(k,0,sizeof(k));
	n = 0,q = 0;
	k[0].val = -1,k[0].num = -1,k[0].ans = -1;
	
   scanf("%lld%lld",&n,&q);
	for(ll i = 1; i <= n; ++i)
		scanf("%lld",&a[i]);
	for(ll i = 1; i <= q; ++i){
		scanf("%lld",&k[i].val);
		k[i].num = i;
	}
	
	sort(a+1,a+1+n);							//对原数组及查询数组排序 
	sort(k+1,k+1+q,cmp1);
	
	add[n] = a[n];
	for(ll i = n-1; i >= 1; --i){				//后缀和 
		add[i] += add[i+1] + a[i];
	}
	for(ll i = 1; i <= n; ++i){					//平均数 
		avg[i] = 1.0 * add[i] / (n-i+1);
	}
	return;
}

void print(){
	sort(k+1,k+1+q,cmp2);
	for(ll i = 1; i <= q; ++i)
		printf("%lld ",k[i].ans);
	putchar('\n');
}

void process(){
	ll p = 1,sum = n;
	for(ll i = 1; i <= n && p <= q;){
		while(a[i] < avg[i] - k[p].val)++i;		//比较 a[i] 与 avg[i] - k[p] 的关系 
		k[p].ans = n-i+1;						//满足条件即记录 ans 
		p++;									//多次查询优化 
	}
	print();
	return;
}

int main(){
	int T;
	scanf("%d",&T); 
	while(T--){
		init();
		process();
	}
	return 0;
}

upd:

2021.11.28 修改代码里的一些小错误(两个主函数？)

2021.12.17 将 Sol1.5 里的证明修正了一下

2021.12.18 又修了点排版错误淦