理解题目
本题要求找使最高的山和最低的山之间的差值不超过17,还要使花费最少
确定算法
一开始我想直接对列表排序,用最高值减最低值得到差值,两边都减差值的均值,这样忽略了只减最高值或最低值的情况,并且只能减整数,均值不是整数的情况难处理,排除这种方法。
这题应该用贪心更好做,枚举所有可能的上界和下界,大于上界的山就减到上界的大小,计算花费;下界同理。记录不同上下界的花费,找最低即可
实现代码
withopen('skidesign.in','r')asfin:n=int(fin.readline())hill=[int(fin.readline())for_inrange(n)]min_money=float('inf')forLinrange(min(hill),max(hill)-17+1):R=L+17money=0forhinhill:ifh>R:money+=(h-R)*(h-R)elifh<L:money+=(h-L)*(h-L)else:continuemin_money=min(money,min_money)#print(f"{R}:{min_money}")withopen('skidesign.out','w')asfout:fout.write(str(min_money)+'\n')