逛街
题目描述
小蒜喜欢逛街。但是小蒜时间有限，只有 \(T\) 个单位时间。小蒜从 \(1\) 号店出发，从 \(1\) 号店走到第 \(i\) 号店需要花费 \(a_{i}\) 个单位的时间，这些店形成了一条直线，因此小蒜从 \(i\) 号店到 \(i+1\) 号店花费的时间为 \(a_{i+1}- a_{i}\)。若选择进去逛，则需要花费 \(b_{i}\) 的时间。对于第 \(i\) 家店，小蒜对其有个评估值 \(c_{i}\)，表示自己是否喜欢这家店。小蒜想在有限的时间内，逛无限的街，当然这是不可能的。它有个目标，将走进去逛的店中 \(c_{i}\) 的和加起来，要使得这个值大于等于 \(k\)，在此基础上，能逛的店越多越好。它想知道最多能逛多少店。若无法满足小蒜的要求，输出 \(-1\)。
输入格式
第一行三个整数 \(n(1\le n\le 300000)\)，\(T(1\le T\le 10^9)\)，\(k(0\le k\le n)\)。
接下来一行 \(n\) 个整数，表示 \(a_{i}(a_{1}=0,a_{1}<a_{2}<\cdots<a_{n}\le 10^9)\)。
接下来一行 \(n\) 个整数，表示 \(b_i(1\le b_{i}\le 10^9)\)。
接下来一行 \(n\) 个整数，表示 \(c_{i}(0\le c_{i}\le 1)\)。
输出格式
输出一行表示答案。
题解
通过观察数据范围可知 \(c_i\) 只能等于 \(0\) 或 \(1\)，小蒜只有 \(T\) 的时间，最少 要逛 \(k\) 个 \(c_i = 1\) 的店，剩余的时间 可以逛 \(c_i = 1\) 或 \(c_i = 0\) 的店。
用三个优先队列 \(q_{1},q_{2},q_{3}\) 维护:
-
\(q_{1}\) 存储必须要进的 \(c_{i} = 1\) 的 \(k\) 个店的 最小进店花费
大顶堆， 最多保留花费值最小的\(k\)个\(c_i=1\)，因为花费大的在堆顶，方便快速出堆。
-
\(q_{2}\) 存储除了 \(q_{1}\) 中的店之外还能进的店
打算除了保证上面 \(q_1\)中的必须保证的\(k\)个最少费用店铺外，在第二个限定条件：总的时长\(T\)范围内，尽量多的可以装入的备选店铺最少费用队列。
大顶堆，同\(q_1\),费用高的随时准备出列，在堆顶 -
\(q_{3}\) 存储暂时不能进的店
被前两项排除掉的店，比如在当前的状态下，加上这个店铺，就会导致时间超过\(T\),这样的店铺入店费用放入\(q_3\)
小顶堆：风水轮流转，在当前看来是不能进的店铺，随时情况的变化，可能就成为了能进的店铺，那么需要随时找最小费用的店铺来填充
设置二个变量 \(sum_1,sum_2\),分别表示优先队列 \(q_1,q_2\) 内 \(b_i\) 的和
算法步骤
依次遍历所有店：
- 将 \(c_i = 1\) 的店加入 \(q_1\) 中，当 \(q_{1}\) 中的数量大于 \(k\) 之后我们将 \(q_1\) 中最大的那个数，从 \(q_1\) 中删除，并放入 \(q_2\) 中
- 将 \(c_i = 0\) 的店直接加入 \(q_2\) 中
如果 \(q_{2}\) 中有的时间大于 \(q_{3}\) 的时间那么就可以交换，以便腾出更多的时间来逛更多的商店。
判断 \(q_1\) 中元素个数是否大于 \(k\)，并且 \(sum_1 + a_i <= T\)。如果都满足的话再进行下面操作，否则直接遍历下一家店。
- 计算出小蒜还有多少剩余时间 \(rest = T - sum_1 - a_i\)。
- 如果 \(q_2\) 中有些数大于 \(q_3\) 中的数时，进行交换。使得 \(q_2\) 中的数均小于等于 \(q_3\) 中的最小值。
- 如果 \(sum_2 > rest\)，说明此时要逛 \(q_1,q_2\) 内所有店的时间是大于 \(T\)的，因为 \(q_1\) 内是必须要逛的店，所以只能将 \(q_2\) 中时间花费比较大的店放弃掉。因此一直将 \(q_2\) 中的最大值删除，放入 \(q_3\) 中，直到 \(sum_2 \leq rest\)。
- 因为第三步放弃了逛一些店，剩余时间变多了，这个时候 \(q_3\) 中不能进的店中有些就可能可以进了，因此从 \(q_3\) 中拿出所有满足 \(rest >= sum_2 + q_3.top()\) 的数，并将这些数从 \(q_3\) 中删除，放入 \(q_2\) 中，并且维护 \(sum_2\)。
- 如果此时 \(rest >= sum2\)，那么当前可以逛的店的数量为 \(k + q_2.size()\)，不断维护结果最大值即可。
参考代码
// https://www.jisuanke.com/problem/T3690
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int a[N], b[N], c[N], n, k;
int T;
// ① 我喜欢的，可以对于k变量每个贡献1的店铺
// ② 用一个大顶堆，以访问需要的时长b[i]为权值，保证这个堆的数量最多是k,那么堆顶的肯定花费时间更长的店,不划算的，准备放弃掉的店铺
priority_queue<int> q1;
// 被筛选下来的，准备放弃掉的店铺，放入到q2里
// 也是一个大顶堆
priority_queue<int> q2;
priority_queue<int, vector<int>, greater<int>> q3; // 小顶堆
LL res = -1; // 结果的默认值是-1
int sum1; // k个代价最小的店铺，加在一起的总的访问花费时间。也就是q1中保留店铺的花费数字和
int sum2; // 被淘汰下来的店铺，放在q2里，q2中店铺的花费数字和
int main() {
freopen("street.in", "r", stdin);
freopen("street.out", "w", stdout);
cin >> n >> T >> k;
for (int i = 1; i <= n; i++) cin >> a[i]; // 从1号店到i号店需要的时间
for (int i = 1; i <= n; i++) cin >> b[i]; // 进入每个店内需要花费的时间
for (int i = 1; i <= n; i++) cin >> c[i]; // 每个店是不是喜欢的
for (int i = 1; i <= n; i++) { // 一次枚举每个店
if (c[i]) { // 如果当前店铺是我喜欢的
q1.push(b[i]); // q1里放入①我喜欢的，②在优先队列中记录进入此店铺i中需要花费的时间
sum1 += b[i]; // sum1:记录进入所有k个以内店铺时，需要的时间花费总和
if (q1.size() > k) { // 如果q1里面的个数已经达到k个，那么就需要有某个店铺出队列
int x = q1.top(); // 因为是大顶堆，所以是堆顶元素出队列
q1.pop(); // 出队列
sum1 -= x; // 维护好sum1
q2.push(x); // 将q1中不是最优解的店移动到q2中去
sum2 += x; // 维护好q2中sum2的和
}
} else { // 如果当前店铺不是我喜欢的
q2.push(b[i]); // 直接放到q2里去
sum2 += b[i]; // 维护好q2中sum2的和
}
if (q1.size() < k) continue; // 如果还不够k个，就继续考查下一个店铺
if (sum1 + a[i] > T) continue; // 如果当前的第i个店铺，如果选择中就超出时间限制T,那没法选择i号店铺
int r = T - sum1 - a[i]; // 剩余的时间
// 不断交换q2中最大的 和 q3中最小的，使得q2中都是代价小的，q3中都是代价大的
while (q3.size() && q3.top() < q2.top()) {
int x = q2.top();
q2.pop();
q2.push(q3.top());
sum2 -= x;
sum2 += q3.top();
q3.pop();
q3.push(x);
}
// 剩余的时间不足以把q2中所有元素都访问到
while (q2.size() && r < sum2) {
int x = q2.top();
q3.push(x);
sum2 -= x;
q2.pop(); // 把q2中顶部最大的元素放到q3里去
}
while (q3.size() && r >= sum2 + q3.top()) {
int x = q3.top();
q2.push(x);
sum2 += x;
q3.pop();
}
// q.size()这个东东如果需要和int之类做加法，必须加上强制转换
if (r >= sum2 && k + (int)q2.size() > res) res = k + (int)q2.size();
}
printf("%lld\n", res);
return 0;
}