codeforces #413 C. Fountains (BIT维护前缀max)

题目链接

题意:有2种货币,分别为C和D.给出n种资源的代价和美丽度,每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买2个资源,问最大美丽度,不能的话输出0.

思路:首先显然三种情况。。。CC,CD,DD.

CD直接扫一遍。。重点是CC和DD

一开始思路错掉了。。全程写two pointer wa4…一直调。。

最后恍然大悟。。发现two pointer非常错啊。。。

其实正解也很简单?

先去跑步了orz

只要想办法维护每个代价的最大美丽度就好了(更准确得说,是维护小于等于某代价的最大美丽度)

直接BIT搞。维护一个前缀max…好像很稳啊?

不过我竟然对于BIT能维护前缀max吃了一惊?

以往都是用线段树来做这个操作的…想想大概是。。我把BIT的函数起名叫”Sum”的锅。。。

看起来就只能求Sum。。。。233333

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz