题解 | 小苯的水果园

解题思路
统计每种果子的数量：用数组 cnt[种类] 记录。
转换为数量分布：freq[数量] = 有多少种类的果子数量等于该值。
前缀和计算剩余：
第 i 天打掉的果子数 = i × freq[i]，
前 i 天累计打掉 = 前缀和，
第 i 天剩余 = 总果子数 - 前缀和。
回答询问：
若询问天数 d 超过最大数量 max_freq，剩余为 0；
否则直接输出预处理好的剩余数。
时间复杂度：O(n + max_freq)，可处理 2×10^5 数据。

#include <stdio.h>
#include<stdlib.h>

#define MAXV 1000001

long long m[MAXV];
int freq[MAXV];
int fruit_num[MAXV];

int main() {
    int t;
    scanf("%d",&t);

    for(int i=0;i<t;i++){
        int n,q;
        scanf("%d %d",&n,&q);

        getchar();
        int a[n+1],d[q+1];

        for(int num=1; num<=n; num++) scanf("%d", &a[num]);
        for(int num_n=1; num_n<=q; num_n++) scanf("%d", &d[num_n]);
        
        int *used_ids =(int*)malloc((n+1)*sizeof(int));
        int used_cnt = 0;        

        int max_id=0;
        
        for(int x=1;x<=n;x++){
            if(m[a[x]]==0){
                used_ids[used_cnt++]=a[x];
            }

            if(a[x]>max_id)max_id=a[x];
            m[a[x]]++;
        }

       
        int max_freq=0;
        for(int id=1;id<=max_id;id++){
            if(m[id]>0){
                freq[m[id]]++;
                if(m[id]>max_freq)max_freq=m[id];
            }
        }

       
        for(int y=1;y<=max_freq;y++){
            n=n-y*freq[y];
            fruit_num[y]=n;
        }

        for(int day=1;day<=q;day++){
            if(d[day]>max_freq){
                printf("0 ");
            }else{
                printf("%d ",fruit_num[d[day]]);
            }
        }

        for(int j=0;j<used_cnt;j++){
            int id=used_ids[j];
            int cnt=m[id];
            m[id]=0;
            freq[cnt]=0;
        }
        printf("\n");

        free(used_ids);
    }
    return 0;
}