NC17315背包哪里购买最优惠？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1403个文字，预计阅读时间需要6分钟。
题目链接：+ 题目 + 题目描述 + Applese有 + (1) + 个容量为 + (v) + 的背包，有 + (n) + 个物品，每个物品有一个价值 + (a_i) + ，以及一个大小 + (b_i) + 。然后他提出了自己的疑问，例如：如果我不装某个物品呢？
题目链接
题目题目描述
Applese有 \(1\) 个容量为 \(v\) 的背包，有 \(n\) 个物品，每一个物品有一个价值 \(a_i\) ，以及一个大小 \(b_i\)
然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装 \(m\) 个物品，要使得求出来的物品价值的中位数最大
Applese觉得这个题依然太菜，于是他把这个问题丢给了你
当物品数量为偶数时，中位数即中间两个物品的价值的平均值
输入描述
第一行三个数 \(v, n, m\) ，分别代表背包容量，物品数量以及需要取出的物品数量
接下来n行，每行两个数 \(a_i,b_i\) ，分别代表物品价值以及大小
\(n ≤ 1e5, 1 ≤ m ≤ n, a_i ≤ 1e9, v ≤ 1e9, b_i ≤ v\)
输出描述
仅一行，代表最大的中位数
示例1
输入
20 5 3
3 5
5 6
8 7
10 6
15 10
输出
8
题解
知识点：优先队列，贪心，二分。
由于要求的长为 \(m\) 的序列的中位数最大值，直接从 \(n\) 个数里枚举 \(m\) 个数会很困难。用dp解决的话，每种可能都要记录还要求一下中位数，也是不可行的。
但是因为是中位数，所以换一种角度，把每个数当作中位数，去匹配一组使其成为中位数的序列。这是很好处理的，只要比这个数小的数存在一定数量个，比这个数大的数存在一定数量个即可，然后从其中取得最小的一组序列重量值，因为我们不关心除了中位数的其他数的价值。
具体地说，我们先考虑 \(m\) 为奇数，那么一个数左右侧都需要有 \(\lfloor \frac{m}{2} \rfloor\) 个数，取他们重量最小值。因此为了使得枚举中位数更加方便，我们先从小到大排序价值，然后从左往右遍历维护一个长度为 \(\lfloor \frac{m}{2} \rfloor\) 的按重量的小顶堆，并在过程中维护动态前 \(\lfloor \frac{m}{2} \rfloor\) 小的和 \(s1[i]\) ，即可得到 \([1,i]\) 中重量前 \(\lfloor \frac{m}{2} \rfloor\) 小的和 。同理从右到左维护一个 \(s2[i]\) ，即 \([i,n]\) 中重量前 \(\lfloor \frac{m}{2} \rfloor\) 小的和。
之后我们对每个数进行判断 s1[i - 1] + a[i].b + s2[i + 1] <= v ，满足的即合法，那么就可以参与最大值的判断。
接下来考虑 \(m\) 为偶数，因为偶数序列中位数是中间两个数之和取下整，因此我们要考虑两个数，一个数维护左侧，一个数维护右侧。那先枚举左边的数，而另一个数因为只需要考虑右侧重量和，由于价值会从左往右递增，而最小重量和一定是递增的（假设一定满足中位数的右侧个数需求），那么会存在一个点使得右侧数字不能成为中位数，左侧数字可以成为中位数但比这个数小，即符合单调性可以二分求解。要注意的是前后缀最小重量和在偶数情况维护的是前 \(\lfloor \frac{m}{2} \rfloor - 1\) 小个。
时间复杂度 \(O(n\log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>
#define ll long long
using namespace std;
int v, n, m;
struct node {
int a, b;
}a[100007];
ll s1[100007], s2[100007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> v >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i].a >> a[i].b;
sort(a + 1, a + n + 1, [&](node a, node b) {return a.a < b.a;});
priority_queue<int> pq;
for (int i = 1;i <= n;i++) {///k小前缀和，维护中位数左侧
s1[i] = s1[i - 1] + a[i].b;
pq.push(a[i].b);
if (pq.size() > m / 2 - !(m & 1)) {
s1[i] -= pq.top();
pq.pop();
}
}
while (!pq.empty()) pq.pop();
for (int i = n;i >= 1;i--) {///k小后缀和，维护中位数右侧
s2[i] = s2[i + 1] + a[i].b;
pq.push(a[i].b);
if (pq.size() > m / 2 - !(m & 1)) {
s2[i] -= pq.top();
pq.pop();
}
}
int ans = 0;
if (m & 1) {///奇数直接枚举中位数
for (int i = m / 2 + 1;i <= n - m / 2;i++)
if (s1[i - 1] + a[i].b + s2[i + 1] <= v)
ans = max(ans, a[i].a);
}
else {///偶数枚举一个之后，二分另一个
for (int i = m / 2;i <= n - m / 2;i++) {
if (s1[i - 1] + a[i].b + s2[i + 1] <= v) {///小优化
int l = i + 1, r = n - m / 2 + 1;
while (l <= r) {
int mid = l + r >> 1;
if (s1[i - 1] + a[i].b + a[mid].b + s2[mid + 1] <= v) l = mid + 1;
else r = mid - 1;
}
if (r > i)ans = max(ans, a[i].a + a[r].a >> 1);///不一定找得到
}
}
}
cout << ans << '\n';
return 0;
}
本文共计1403个文字，预计阅读时间需要6分钟。
题目链接：+ 题目 + 题目描述 + Applese有 + (1) + 个容量为 + (v) + 的背包，有 + (n) + 个物品，每个物品有一个价值 + (a_i) + ，以及一个大小 + (b_i) + 。然后他提出了自己的疑问，例如：如果我不装某个物品呢？
题目链接
题目题目描述
Applese有 \(1\) 个容量为 \(v\) 的背包，有 \(n\) 个物品，每一个物品有一个价值 \(a_i\) ，以及一个大小 \(b_i\)
然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装 \(m\) 个物品，要使得求出来的物品价值的中位数最大
Applese觉得这个题依然太菜，于是他把这个问题丢给了你
当物品数量为偶数时，中位数即中间两个物品的价值的平均值
输入描述
第一行三个数 \(v, n, m\) ，分别代表背包容量，物品数量以及需要取出的物品数量
接下来n行，每行两个数 \(a_i,b_i\) ，分别代表物品价值以及大小
\(n ≤ 1e5, 1 ≤ m ≤ n, a_i ≤ 1e9, v ≤ 1e9, b_i ≤ v\)
输出描述
仅一行，代表最大的中位数
示例1
输入
20 5 3
3 5
5 6
8 7
10 6
15 10
输出
8
题解
知识点：优先队列，贪心，二分。
由于要求的长为 \(m\) 的序列的中位数最大值，直接从 \(n\) 个数里枚举 \(m\) 个数会很困难。用dp解决的话，每种可能都要记录还要求一下中位数，也是不可行的。
但是因为是中位数，所以换一种角度，把每个数当作中位数，去匹配一组使其成为中位数的序列。这是很好处理的，只要比这个数小的数存在一定数量个，比这个数大的数存在一定数量个即可，然后从其中取得最小的一组序列重量值，因为我们不关心除了中位数的其他数的价值。
具体地说，我们先考虑 \(m\) 为奇数，那么一个数左右侧都需要有 \(\lfloor \frac{m}{2} \rfloor\) 个数，取他们重量最小值。因此为了使得枚举中位数更加方便，我们先从小到大排序价值，然后从左往右遍历维护一个长度为 \(\lfloor \frac{m}{2} \rfloor\) 的按重量的小顶堆，并在过程中维护动态前 \(\lfloor \frac{m}{2} \rfloor\) 小的和 \(s1[i]\) ，即可得到 \([1,i]\) 中重量前 \(\lfloor \frac{m}{2} \rfloor\) 小的和 。同理从右到左维护一个 \(s2[i]\) ，即 \([i,n]\) 中重量前 \(\lfloor \frac{m}{2} \rfloor\) 小的和。
之后我们对每个数进行判断 s1[i - 1] + a[i].b + s2[i + 1] <= v ，满足的即合法，那么就可以参与最大值的判断。
接下来考虑 \(m\) 为偶数，因为偶数序列中位数是中间两个数之和取下整，因此我们要考虑两个数，一个数维护左侧，一个数维护右侧。那先枚举左边的数，而另一个数因为只需要考虑右侧重量和，由于价值会从左往右递增，而最小重量和一定是递增的（假设一定满足中位数的右侧个数需求），那么会存在一个点使得右侧数字不能成为中位数，左侧数字可以成为中位数但比这个数小，即符合单调性可以二分求解。要注意的是前后缀最小重量和在偶数情况维护的是前 \(\lfloor \frac{m}{2} \rfloor - 1\) 小个。
时间复杂度 \(O(n\log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>
#define ll long long
using namespace std;
int v, n, m;
struct node {
int a, b;
}a[100007];
ll s1[100007], s2[100007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> v >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i].a >> a[i].b;
sort(a + 1, a + n + 1, [&](node a, node b) {return a.a < b.a;});
priority_queue<int> pq;
for (int i = 1;i <= n;i++) {///k小前缀和，维护中位数左侧
s1[i] = s1[i - 1] + a[i].b;
pq.push(a[i].b);
if (pq.size() > m / 2 - !(m & 1)) {
s1[i] -= pq.top();
pq.pop();
}
}
while (!pq.empty()) pq.pop();
for (int i = n;i >= 1;i--) {///k小后缀和，维护中位数右侧
s2[i] = s2[i + 1] + a[i].b;
pq.push(a[i].b);
if (pq.size() > m / 2 - !(m & 1)) {
s2[i] -= pq.top();
pq.pop();
}
}
int ans = 0;
if (m & 1) {///奇数直接枚举中位数
for (int i = m / 2 + 1;i <= n - m / 2;i++)
if (s1[i - 1] + a[i].b + s2[i + 1] <= v)
ans = max(ans, a[i].a);
}
else {///偶数枚举一个之后，二分另一个
for (int i = m / 2;i <= n - m / 2;i++) {
if (s1[i - 1] + a[i].b + s2[i + 1] <= v) {///小优化
int l = i + 1, r = n - m / 2 + 1;
while (l <= r) {
int mid = l + r >> 1;
if (s1[i - 1] + a[i].b + a[mid].b + s2[mid + 1] <= v) l = mid + 1;
else r = mid - 1;
}
if (r > i)ans = max(ans, a[i].a + a[r].a >> 1);///不一定找得到
}
}
}
cout << ans << '\n';
return 0;
}