python/TangDou/JiShuanKe/2023-02-17/T3690.md

逛街

题目描述

小蒜喜欢逛街。但是小蒜时间有限，只有 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 的和

算法步骤

依次遍历所有店：

1. 将 c_i = 1 的店加入 q_1 中，当 q_{1} 中的数量大于 k 之后我们将 q_1 中最大的那个数，从 q_1 中删除，并放入 q_2 中
2. 将 c_i = 0 的店直接加入 q_2 中

如果 q_{2} 中有的时间大于 q_{3} 的时间那么就可以交换，以便腾出更多的时间来逛更多的商店。

判断 q_1 中元素个数是否大于 k，并且 sum_1 + a_i <= T。如果都满足的话再进行下面操作，否则直接遍历下一家店。

1. 计算出小蒜还有多少剩余时间 rest = T - sum_1 - a_i。
2. 如果 q_2 中有些数大于 q_3 中的数时，进行交换。使得 q_2 中的数均小于等于 q_3 中的最小值。
3. 如果 sum_2 > rest，说明此时要逛 q_1,q_2 内所有店的时间是大于 T的，因为 q_1 内是必须要逛的店，所以只能将 q_2 中时间花费比较大的店放弃掉。因此一直将 q_2 中的最大值删除，放入 q_3 中，直到 sum_2 \leq rest。
4. 因为第三步放弃了逛一些店，剩余时间变多了，这个时候 q_3 中不能进的店中有些就可能可以进了，因此从 q_3 中拿出所有满足 rest >= sum_2 + q_3.top() 的数，并将这些数从 q_3 中删除，放入 q_2 中，并且维护 sum_2。
5. 如果此时 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;
}