zd的小窝
0%

THUPC-2023 众数 题解

发表于

一.题意简述

现在有若干个数，值域为 $[1,n]$ ，其中大小为 $i$ 的数有 $a_i$ 个，现在重排这个序列使得前缀众数之和最大。

众数在这个题定义为：数列中出现最多的数，如果有出现次数一样的以最大的为众数。

二.题目分析

考虑贪心。

我们肯定要让大的数出现的次数尽可能多，而这么做一定是尽量的让大的数成为众数的次数尽可能多。

我们很容易想到这样一种方案：

  1. 以最大数的开头依次递减排列。
  2. 如果一个数被用完了就跳过这个数。

比如样例我们就可以排列为 $(3,2,1,3,2,2)$ ，众数分别为 $(3,3,3,3,3,2)$

证明的话很简单，随机交换这个数列中的某一项都会使得总和变小。

接下来问题就变成了怎么计算出题目要求的前缀众数和。

以 $i$ 为例，我们设第 $j$ 个数出现的次数为 $s_j (j \le n)$，我们需要找到以 $i$ 为众数的数列的长度，而这个数列一定是由比 $i$ 小的数组成，（比 $i$ 大的数我们已经在前一次用完）更进一步，其由两部分组成：

  1. 出现次数比 $i$ 多的数贡献出 $s_i$ 的长度，自身还剩下 $s_j-s_i$ 个。
  2. 出现次数比 $i$ 少的数贡献出 $s_j$ 的长度，自身被用完。

我们考虑分开计数，最后再加起来（详细见代码）。

注意我们需要记录当前用的数最多用了几次，如果有次数比这个小的应该舍去。

三.代码时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
	Author:zd
	Status:WA on pretest 2
	note: 只保留了主函数部分
*/
int n,m,k,cnt,a[N],b[N],sum[N];
signed main(){
    read(n);
    for(int i=1;i<=n;i++)read(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    int ans=0;
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];
    for(int i=n;i>=1;i--){
        int num=a[i];
        if(cnt>=num)continue;//如果已经被用完
        int pos=lower_bound(b+1,b+1+n,num)-b;//找到比i出现次数大的数的位置
        int pos2=upper_bound(b+1,b+1+n,cnt)-b;//比当前次数小的数的位置
        ans+=(sum[pos-1]-sum[pos2-1]-(pos-pos2)*cnt)*i;//比i小的数量
        ans+=((n-pos+1)*(a[i]-cnt))*i;//比i多的数量
        cnt=a[i];//更新使用次数
    }
    writeh(ans);
    return 0;
}