网站建设的具体流程图,网站设计制作ihanshi,做网站的计划书,南京哪家公司做企业网站 做得比较好题目大意
给定 n n n个数 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an#xff0c;你需要找到一个集合 S S S#xff0c;使得 S S S中严格大于 S S S的平均数的数字个数尽量多#xff0c;输出最多的个数。
注意#xff1a;这里的集合是可重集#xff0c;…题目大意
给定 n n n个数 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an你需要找到一个集合 S S S使得 S S S中严格大于 S S S的平均数的数字个数尽量多输出最多的个数。
注意这里的集合是可重集数字可以重复。 1 ≤ n ≤ 1 0 6 , 1 ≤ a i ≤ 1 0 9 1\leq n\leq 10^6,1\leq a_i\leq 10^9 1≤n≤106,1≤ai≤109 题解
首先我们将 a a a从小到大排序。
枚举第一个严格大于 S S S的平均数的数 i i i。因为比平均数小的数肯定越多越好所以我们可以取 1 1 1到 i − 1 i-1 i−1之间的所有数。
为了让平均数尽量小在选择严格大于 S S S的平均数的数的时候肯定要选尽量小的数。也就是说严格大于 S S S的平均数的数是 a i a_i ai和 a i a_i ai之后的连续的一段数设这段数是 a i a_i ai到 a p a_p ap那也就是说我们要选择的数是 a 1 a_1 a1到 a p a_p ap这里的 p p p需要满足 s u m p p a i \dfrac{sum_p}{p}a_i psumpai其中 s u m p p \dfrac{sum_p}{p} psump指这 p p p个数的平均数也就是 s u m p a i × p sum_pa_i\times p sumpai×p。为了使严格大于 S S S的平均数的数更多我们需要求满足条件的最大的 p p p。
我们发现满足条件的最大的 p p p是随 i i i的增大而增大或者不变的那么我们可以用一个指针来求 p p p。对于每个 i i i和其对应的 p p p严格大于 S S S的平均数的数的数量为 p − i 1 p-i1 p−i1用 p − i 1 p-i1 p−i1来更新答案即可。
时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
code
#includebits/stdc.h
using namespace std;
const int N1000000;
int n,p1,ans0,a[N5];
long long sum[N5];
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}sort(a1,an1);for(int i1;in;i){sum[i]sum[i-1]a[i];}for(int i1;in;i){while(p1nsum[p1]1ll*(p1)*a[i]) p;ansmax(ans,p-i1);}printf(%d,ans);return 0;
}
