补题 [2023牛客寒假算法基础集训营1] 现在是，学术时间 (I)

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

北京IT大学（BIT）计算机学院为了在下一轮学科评估中让计算机学科获得$A+$的评定结果，进行了如引进强大的老师、加强课程之类、提高授课质量等多方面的努力。而为了提高学科评估中，学术成果一项的得分，计算机学院的院长打算通过重新分配论文的方式使得学院里所有教授的H指数值之和尽可能大。

具体来说，H指数用于粗略的评估一位教授的学术水平。一位教授可以发表多篇论文，每篇论文有一个引用量。定义一位教授的H指数为使得”该教授发表的所有论文中，有至少 $H$ 篇论文的引用量大于等于 $H$ “这一命题成立的最大的 $H$ 。

现在，院长发现学院里的每位老师当前的发表文章数都为 $0$ ，且恰好每人都有一篇写好的论文未发表，由于院长很懂学术界，他也可以准确的预知到每篇文章发表后的引用量。院长决定以最优的方式重新分配这些论文，他可以任意指定一篇论文由哪位教授发表。规定每篇论文只能被一位教授发表，一位教授可以发表多篇论文。

假设重新分配并发表后第iii位教授的H指数为 $h_i$​，院长希望最大化$\Sigma_{i=1}^nh_i$​，即所有教授的H指数之和最大。请你帮院长计算出这一最大的值为多少。

输入描述

输入第一行为一个正整数 $T(1\leq T\leq 10^5)$，表示样例组数。

每组样例包括两行。

第一行是一个正整数$ n(1\leq n \leq 10^5)$，表示北京IT大学计算机学院的教授数量；第二行包括 $n$ 个非负整数，第 $i$ 个数字 $a_i(0\leq a_i \leq 10^9)$ 表示第 $i$ 位教授写好但未发表的文章在发表后会获得的引用量。

保证每组数据所有用例的 $n$ 之和 $\Sigma n \leq 5\times 10^5$ 。

输出描述

对于每组样例，输出一个整数，表示 $\Sigma_{i=1}^nh_i$ 最大的值为多少。

输入

1
2
3
4
5
2
3
6 5 4
2
10 0

输出

1
2
3
1

说明

对于样例一，一种可能的方案是把三篇论文（引用量分别为$6,5,4$）都让第一个教授发表，这样第一个教授有三篇引用量大于等于三而没有四篇引用量大于等于四，因此有$h_1=3,h_2=0,h_3=0$，可以证明此时有$\Sigma_{i=1}^nh_i$最大，其值为$3$。

题解

题目解析

一道诈骗题,实际上是输出非0个数的数量.

具体原因可以这么解释:

  • 首先根据H指数的定义(有至少H篇论文的引用量大于等于H)可得,H指数和存在最大上界,即所有的非0个数的和.
  • 如果每个人只投稿自己的论文,那必然可以得到H指数的最大值.也就是所有的非0个数的和.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
typedef long long ll;

MAXN(1e5);
int a[MAXN];

signed main(){
	CIN;CIN_;
	int T;
	cin >> T;
	while(T--){
		int n,cunt=0;
		cin >> n;
		cin(n,a);
		fa(1,n,1){
			if(a[i] != 0) cunt++;
		}
		cout << cunt << endl;
	}
	return 0;
}