[CodeForces 3B Lorry]【另类背包】【排序、贪心、双指针维护】

【题目链接】http://www.codeforces.com/problemset/problem/3/B

【题目大意】

给定一个容量为v<=10^9的背包和n<=10^5个物品。

每个物品有一个体积(1<=ti<=2)和价值(1<=pi<=10^4)。

每个物品只能装一次，问最多能装多少价值的东西。

【算法分析】

一开始看的时候2了一下。。。还想到把体积为1的和成体积为2的然后根据奇偶性讨论一下。

然后后来重新一想发现实在太2了。

就是把体积为1和体积为2的放进两个数组里面，然后按价值从大到小排序。

然后用两个指针利用单调性维护可以很容易得出当取i个体积为1的物品时，答案最大能是多少。

于是就解决了。

【其它】

用桶排可以做到总复杂度O(n)

【CODE】

http://xiudaima.appspot.com/code/detail/4348006