题解：P17003 [NWERC 2019] 极速魔方 / Expeditious Cubing

题外话

Claire 这人玩得挺六（在样例中）。这家伙平均七秒复原一个魔方，属于超级超级顶尖的水平了，不愧是国际级选手。不像我平均二十秒都难。

细节：

输入中的所有时间都在111到202020之间，包含端点。

Claire 一秒能复原？

没事，这反正是算法竞赛，脱离现实。

题解：P17003 [NWERC 2019] 极速魔方 / Expeditious Cubing

题意

给定一个444个数的数组和一个目标值。

你需要算出第555个数，使得这个数组去掉最大和最小的两个极值后剩余的333个数的平均数不大于这个目标值。

• 若第555个数是啥都可以，输出infinite；
• 若第555个数是啥都不能满足条件，输出impossible；
• 否则输出第555个数最大可能是几。

思路

分类讨论即可。

一定赢的情况

一定赢，就是这人即使玩得很差，也可以赢。

这人玩得很差，但是只取三次成绩，所以这个数组中较大的三个数的平均值不大于目标值那么就一定赢。

一定输的情况

一定输，就是这人即使玩得很好，也是输。

这人玩得很好，但是只取三次成绩，所以这个数组中较小的三个数的平均值大于目标值那么就一定输。

算出第555个数

不是一定输，也不是一定赢，那么就要算出第555个数是几了。

我们不妨把排序后数组称作aaa，就是我们要求的数称作xxx。

首先，一定是a0≤x≤a4a_0\le x\le a_4a0​≤x≤a4​。因为若xxx不在这个取件范围之内，那么一定是必输或必赢的状态。

xxx最大是几呢？很明显，xxx与a1a_1a1​、a2a_2a2​的平均数一定要不大于ttt。

所以xxx最大就是：

3t−a1−a23t-a_1-a_23t−a1​−a2​

为了避免精度问题，不要用除法。

代码

#include<stdio.h>#include<algorithm>usingnamespacestd;inta[4],t;doublek;intmain(){for(inti=0;i<4;i++)scanf("%lf",&k),a[i]=k*100+0.5;// + 0.5 是为了防止精度问题，下同sort(a,a+4),scanf("%lf",&k),t=k*300+0.5;if(a[0]+a[1]+a[2]>t){puts("impossible");return0;}if(a[1]+a[2]+a[3]<=t){puts("infinite");return0;}printf("%.2f\n",(t-a[1]-a[2])/100.);return0;}