晚测2

T1

一道精妙的思维题,遇到这种画画柱状图也许帮助比较大。

首先考虑最优的情况怎么取,每次从最高的选两个然后再从次高的选一个这样一定不劣,所以就有了60分暴力,考虑怎么优化它,可以认为,从最高的拿出两个,将它理解为先从最高的拿出一个,变成最低的,然后从三堆里各取一个,这样变换的话最后结果显然会是(lfloor frac{a+b+c}{3} floor),因为像上边那么变的话三堆其实是没有区别的。

但是这样实际上并不对,因为还有一种情况,上述变换中有可能最高的那一堆到最后也不会发生变化,最后答案就是较小两堆的和。

T2

应该比较简单吧,一定不会有(No)的情况,因为可以将离得近的两点分别配对,使得各点间的路径没有交集,这样一定不会大于(n),但是这样做时间复杂度会高,因为它只说不大于(n)就行,所以直接排序按照(DFS)序取就行了。

int - > long long 0 - > 100
原文地址:https://www.cnblogs.com/anyixing-fly/p/13769678.html