L - Candy Machine

SDUT 2022 Spring Team Contest(for 21) - 12 - Virtual Judge

JB loves candy very much.

One day, he finds a candy machine with NN candies in it. After reading the instructions of the machine, he knows that he can choose a subset of the NN candies. Each candy has a sweet value. After JB chooses the subset, suppose the average sweet value of the chosen candies is XX, all the candies with sweet value strictly larger than XX will belong to JB. After JB makes the choice, the machine will disappear, so JB only has one opportunity to make a choice.

JB doesn't care how sweet the candies are, so he just wants to make a choice to maximize the number of candies he will get. JB has been fascinated by candy and can't think, so he needs you to help him.

Input

The first line contains one integer NN (1\leq N\leq 10^61≤N≤106), denoting the number of candies in the machine.

The second line contains NN integers a_1,a_2,\dots,a_Na1​,a2​,…,aN​ (1\leq a_i\leq 10^91≤ai​≤109), denoting the sweet values of the candies.

Output

One integer, denoting the maximum number of candies JB can get.

Sample 1

Inputcopy	Outputcopy
5 1 2 3 4 5	2

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int a[N];
signed main()
{
    int n;
    scanf("%lld",&n);
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    sort(a+1,a+1+n);//二分之前需要排序
    int ans=0;
    double average=sum*1.0/n*1.0;
    for(int i=1;i<=n;i++)
    {
        if((double)a[i]>average)ans++;
    }
    for(int i=n;i>=2;i--)
    {
        sum-=a[i];
        average=sum*1.0/(i-1)*1.0;
        int x=upper_bound(a+1,a+i,average)-a;//二分找到大于average的下标
        ans=max(ans,i-x);
    }
    printf("%lld\n",ans);
    return 0;
}

顺便学了一下upper_bound这个函数，这题的主要思路就是先将这个数组从小到大排序，然后依次比较每次去掉最大的一个数能取糖果的数量，最大的就是结果。因为如果每次去掉是最小的数的话，平均值会变大，取糖果的数量肯定会变小；如果每次去掉的是最大的数的话，平均值会变小，结果就会有变大的可能性。所以每次比较要去掉最大的数。