洛谷P2094 - 运输

  被浏览

这道题第一眼像是合并果子,我们考虑贪心。

我们先选择一种贪心策略:每次选当前最大的两个数合并,直到只剩最后一件物品。

接下来我们证明一下为什么这样是对的:

我们先想一想合并果子,那道题的贪心策略与这道题相反,每次选最小的两个数合并。考虑它为什么是对的——我们发现越先选的数对结果的贡献越大,为了使结果尽可能小,肯定是越小的先选越好。

洛谷P1432 - 倒水问题

  被浏览

很容易看出这是宽度优先搜索,因为要求步数最少,且每个操作代价相同。

我们可以按操作类别分 6 种情况扩展,如果搜到最终状态就跳出 BFS(搜索顺序可以随意,因为 spj 已经配置好了,不像数据修改前要有特定的顺序)。

记得标记已经出现过的情况,不然会 TLE/MLE;

洛谷P2234 - 「HNOI2002」营业额统计

  被浏览

根据题意我们发现对于每个$A_{i}$,与它绝对值最小的一定是前$i$个数排序后在它前面或后面的数。

这样的话,我们维护一个单调的序列,插入每天的营业额时计算其波动值即可。

最暴力的便是插入排序,复杂度$(N^2)$,不能忍受。。

我们应选择复杂度为$(NlogN)$的方法。

维护一个单调序列自然想到了 set(平衡树也可以,但是作者懒,想用 STL 水过去,逃……),因为可能有多个相同的营业额,所以我选择了 multiset。