题解：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​为了避免精度问题不要用除法。代码#includestdio.h#includealgorithmusingnamespacestd;inta[4],t;doublek;intmain(){for(inti0;i4;i)scanf(%lf,k),a[i]k*1000.5;// 0.5 是为了防止精度问题下同sort(a,a4),scanf(%lf,k),tk*3000.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;}