HDU 6438 Buy and Resell

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6438

n(1<=n<=1e5)个城市连成的一条链,商品在第i个城市交易的价格为ai,你从第一个城市不回头的走到第n个城市,在每个城市你可以:

  1. 以ai的价格买入1个商品
  2. 以ai的价格卖出1个商品
  3. 什么也不做

一开始你带着无限多的钱,并且你可以同时携带多个商品。

问你两个问题:

  1. 最大收益
  2. 最大收益前提下的最小交易次数

有点类似于网络流的反向边思想,这个之后再说。

思路:

  1. 前提1:假如在一个城市既买入商品,又卖出商品,相当于什么也没做。所以从1到n讨论每个城市,我要做的是决策怎么交易:买,卖,不买不卖。
  2. 前提2:每走到一个城市,我都买商品,直到我走完所有城市,手上还有囤积的货物,说明当初这些货物本来不该购买。
  3. 前提3:收益=卖价和-买价和=累计收益+囤积货物成本
  4. 我的第一个想法是:讨论到第i个城市时,如果手里买价最低的商品(优先队列维护)价格低于ai时,我就卖出(累加收益),否则我就买入(累加成本)(因为我觉得既买又卖是没有意义的)。显然这是一个错误的算法,甚至连样例1都过不了。错在在第i个城市并不是该卖出商品的地方,说不定最优解并不是在第i个城市卖出商品呐。
  5. 我的第二个想法是:假如在第i个城市卖出商品获得一些收益,我还是要在第i个城市买入1个商品,说不定之后就能转手又赚一笔呐。显然这又是一个错误的算法,甚至还是连样例1都过不了。错在在第i个城市又买又买相当于什么也没做,说不定最优解是在第i个城市买入商品呐。
  6. 我的第三个想法是:假如在第i个城市卖出商品获得一些收益,我在第i个城市买2个商品。这样做的灵感源于网络流问题的反向边思想,在搜索的时候假如反向边,假如决策错误,可以在后面把这个错误决策抵消(反悔)掉。假如我在之后总共卖出了1个现在买入的商品,说明我在这个城市本来该不买也不卖,假如我在之后总共卖出了2个现在买入的商品,说明我在这个城市本来该买入1个商品,假如我在之后没有卖出任何现在买入的商品,说明我在这个城市本来该卖出1个商品。

跑一下样例。bought[i]表示最终在第i个城市买入的商品数量,值可能为0,1,2。sold[i]表示在第i个城市卖出的商品数量,值可能为0,1。

……(没图)

样例2过不了,我这样算出的交换次数是4,错误在于把既买入了9,又卖出了9,然而这两个9还不在同一个城市。我的解决方法是,在优先队列的比较函数上做文章。当两个城市的商品价格相同时,我优先选择卖出过商品的城市的商品(因为这样可以抵消交换次数)

然后我开心地写程序了:

然后WA了……。

错误数据为:

正解为 7 4

我输出 7 6。

问题处在计算最小交换次数上。

输出中间结果

……(没图)

发现这组数据中两个8各卖出1次商品,买入2次商品,然而到达价格10,9两个城市后,都选择了卖出第2各8的商品。正确的选择方法显然是再两个8各买一次商品,抵消掉两个8买入的商品,交换次数为4。然而我这样抵消不了,所有输出6。

考虑为什么发生这种情况,回想之前买入两个商品的原因,就是为了提供一个挽回的途径,但仔细一想,其实这两个商品本质上的意义是有区别的。 也就是之前说的:

假如我在之后总共卖出了1个现在买入的商品,说明我在这个城市本来该不买也不卖,假如我在之后总共卖出了2个现在买入的商品,说明我在这个城市本来该买入1个商品,假如我在之后没有卖出任何现在买入的商品,说明我在这个城市本来该卖出1个商品。

所以考虑标记区分这两个商品,添加一个formiko变量(值为1或2)标记这个商品的种类。之后卖出一个现在买入的商品,会抵消两次交易次数,所以我们把其中一个商品的formiko赋值为2,其他所有商品的formiko赋值为1。

这样,这组样例中,就能分别买入两个8的一个商品,抵消掉多余的交换次数。

以下是AC程序。

 

【模板】树状数组

单点更新,区间查找

 

【模板】输入输出挂

做hdu 6396被卡输出输出了,关键是用输入输出优化都超时,用上了这套输入输出挂,就直接398ms过了

后来了解到做 hdu 5392 速度可能是:输入挂>不优化>输入优化

从这抄来的模板

 

这个地方有浮点数的输入优化,没尝试过,放在这。

 

另外一个板子

 

【模板】AC自动机

 

Eratosthenes筛选法欧拉函数打表

第二种写法更优。

maxn=1e7 第一种写法 0.6s, 第二种写法 0.5s

maxn=1e8 第一种写法 6s,第二种写法5s

Eratosthenes筛法

 

欧拉函数

 

【模板】KMP