AT_cf_2015_morning_easy_c ヘイホー君と最終試験 题解

题目

链接

https://www.luogu.com.cn/problem/AT_cf_2015_morning_easy_c

字面描述

题面翻译

在Coefes大学的比赛编程课上，为了成绩评价，决定进行N次的考试。各考试的成绩，是0以上以上M以下的整数值。N个的考试成绩中，如果分最高的K次测试的平均分是R分以上的话，恭喜你！你被录取了！分最高的K次测试的平均分达不到R分的情况下不合格，你不会被录取。结束了N-1次考试的你，打算参加期末考试。除期末考试外，N-1次的考试中，你的成绩，分别是S1、S2、…SN。你要在期末考试中取得多少分以上的成绩才会被录取？

题目描述

Codefes大学の競技プログラミングの授業では、成績評価のために、$ N $ 回の試験を行うことにしています。 各試験での成績は、$ 0 $ 以上 $ M $ 以下の整数値です。 $ N $ 個の試験成績のうち、上位 $ K $ 個の平均が $ R $ 点以上であれば、めでたく単位が認定されます。 上位 $ K $ 個の平均が $ R $ 点未満の場合には不合格となり、単位は認定されません。

$ N-1 $ 回の試験を終えたヘイホー君は、最終試験に臨もうとしています。 最終試験を除く $ N-1 $ 回の試験におけるヘイホー君の成績は、それぞれ $ S_1 $, $ S_2 $, …, $ S_{N-1} $ 点でした。 ヘイホー君は、最終試験で何点以上取れば単位が認定されるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ K $ $ M $ $ R $ $ S_1 $ $ S_2 $ : $ S_{N-1} $

• $ 1 $ 行目には、整数 $ N\ (1\ ≦\ N\ ≦\ 100) $, $ K\ (1\ ≦\ K\ ≦\ N) $, $ M\ (1\ ≦\ M\ ≦\ 10^9) $, $ R\ (0\ ≦\ R\ ≦\ M) $ が、空白区切りで与えられる。 ここで、$ N $ は試験の回数、$ K $ は成績評価に用いる試験の個数、$ M $ は各試験の満点、$ R $ は単位認定に必要な平均点を表す。
• $ 2 $ 行目以降の $ N-1 $ 行には、整数 $ S_i\ (0\ ≦\ S_i\ ≦\ M) $ が与えられる。これは $ i $ 回目の試験におけるヘイホー君の成績を表す。
• $ S_N $ が与えられないことに注意せよ。

输出格式

出力は $ 1 $ 行からなる。

• 最終試験の結果が何点であってもヘイホー君に単位が認定されるならば、$ 0 $ を出力せよ。
• 最終試験の結果が何点であってもヘイホー君に単位が認定されないならば、$ -1 $ を出力せよ。
• どちらでもない場合、ヘイホー君が最終試験で取る必要のある最低点を出力せよ。

いずれの場合も、出力の末尾には改行をいれること。

样例 #1

样例输入 #1

5 3 100 60
86
23
49
39
1
2
3
4
5

样例输出 #1

45
1

样例 #2

样例输入 #2

5 3 100 60
92
100
95
99
1
2
3
4
5

样例输出 #2

0
1

样例 #3

样例输入 #3

5 3 100 60
18
42
29
31
1
2
3
4
5

样例输出 #3

-1
1

样例 #4

样例输入 #4

13 10 1000000000 645245296
492014535
611893452
729291030
392019922
293849201
474839528
702912832
341845861
102495671
908590572
812912432
129855439
1
2
3
4
5
6
7
8
9
10
11
12
13

样例输出 #4

986132796
1

提示

Sample Explanation 1

ヘイホー君が最終試験で $ 45 $ 点を取った場合、上位 $ 3 $ 個の平均は $ (86+49+45)/3=60 $ となり、単位が認定されます。 もちろん、$ 46 $ 点以上取っても単位は認定されます。 一方、$ 44 $ 点以下の場合には単位が認定されません。

Sample Explanation 2

最終試験で $ 0 $ 点でも単位が認定されます。

Sample Explanation 3

残念ながら、最終試験が満点でも単位は認定されません。

Sample Explanation 4

大きな数が入力されることもあります。オーバーフローに注意しましょう。

代码实现

#include
#define ll long long
using namespace std;

const int maxn=100+10;
int n,k;
ll m,r,cnt;
ll a[maxn];
inline bool cmp(ll x,ll y){return x>y;}
int main(){
	scanf("%d%d%lld%lld",&n,&k,&m,&r);
	--n;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=k;i++)cnt+=a[i];
	//printf("%lld\n",cnt);
	ll op=(ll)k*r;
	if(cnt>=op){
		printf("0\n");
		return 0;
	}
	if(k==n+1){
		ll x=op-cnt;
		if(x>m)printf("-1\n");
		else printf("%lld\n",x); 
		return 0;
	}
	ll x=op-cnt+a[k];
	if(x>m)printf("-1\n");
	else printf("%lld\n",x); 
	return 0;
}
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