YZOJ P3216 行商

YZOJ P3216 行商

时间限制:1000MS      内存限制:262144KB

难度:\(4.0\)

  • 题目描述

有 \(n\) 个货物,每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\),但是载重量仅为 \(m\) 。

挑选出一些货物,总重量不超过 \(m\),使价值之和最大。

  • 输入格式

第一行,两个整数 \(n\),\(m\);

接下来 \(n\) 行,每行两个整数 \(w_i\),\(c_i\) 。

  • 输出格式

一个整数 \(ans\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

 \(1 \leq n \leq 10^6\),\(1 \leq m \leq 4^{31}\),\(1 \leq w_i \leq 3\),\(1 \leq c_i \leq 10^9\) 。

 

 

 


 

 

首先 \(w\) 这么小,肯定是把 \(3\) 种情况分开考虑。

将货物按照 \(w\) 分为 \(3\) 类,分别按从大到小进行排序,然后顺便记个前缀和 \(sum\) 。

发现如果先不考虑 \(w=3\) 的情况,那么有:选 \(i\) 件货物时,有 \(f_i = sum2_i + sum1_{m – 2i}\) 。

可以发现 \(sum2\) 是一个单调上升并且二阶导数 \(<0\) 的整点函数,\(sum1_{m – 2i}\) 是一个单调下降并且二阶导数 \(>0\) 的整点函数。

经过简单的数学推理,可以发现它们相加,结果会是一个单峰函数。

这样就枚举 \(w=3\) 取的数量,然后三分,时间复杂度 \(O(nlogn)\) 。

(p.s. \(m \leq 4^{31}\) 看似很大,但是当 \(m \geq 3n\) 所有的货物都可以装的下,所以并没有什么用)

(貌似还有一种 DP 的做法)

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注