Codeforces Round #760 Trader Problem 题解 (Java/C++)

题解

首先,我们可以直接把所有物品一起考虑。

我们考虑下面的例子(我基于样例改了一点点):

我们考虑k=2时,经过若干次交易之后的结果:

我们仔细观察上面的例子,我们注意到:10-15是连续的一个区间,因为15到18之间的差为3,而10-15之间的所有物品之间的差都不超过k。
而最终的结果,红字必然是从右往左依次排列。
同理18自己是一段,30-31是一段。

现在我们试着把k从2改为3。很自然的,现在整个10-18都会是连续的一整段。于是很自然的:

于是,做法就比较明显了:

  1. 首先,我们离线的处理所有的查询。我们将k从小到大依次处理。
  2. 随着k的逐步增大,我们使用并查集来维护区间。
  3. 对于每个区间,我们记录其最右端的点的下标,以及其区间内物品的数量。
  4. 最后,我们维护一个前缀和以便我们在合并两个区间时,快速计算对最终总价值的影响即可。

代码

Java

Submission #140900904 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #140903723 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论