ACM模版

描述

题解

十分巧妙的一道题，三个优先队列可解。

每次我们枚举终点 end ，这样我们就确定了路上的花费 a[end] ，剩下的就是处理进店的花费 b[i] 。这里我们需要注意的是， c[i]∈{ 0,1} ，所以呢，题目中要求的 k ，也就是必须逛不少于 k 个 c[i]=1 的店。首先我们定义三个优先队列 Q1、Q2、Q3 ， Q1 用于存储进店花费最小的不超过 k 个 c[i]=1 的店， Q2 用于表示除了 Q1 中的店，还可以进入的其他店， Q3 表示除去 Q1、Q2 中的店，剩下的不能逛的店。

贪心搞搞，具体贪心策略可以看代码，注释应该不难理解的。

这里有一个问题是，当我去掉代码中的第一个强制转换时，也就是说改成 k + Q2.size() > ans 会出错，打个比方，当我的 k=1,Q2.size()=0,ans=−1 时，理论上应该是给判真的，可是实际上给我判定的结果为假。很诧异，具体原因还没有找到，希望大神们给出解释。谢谢……

代码

#include <queue>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>

#define ll long long

using namespace std;

const int MAXN = 1e5 + 10;

int n, k;
ll T;
int a[MAXN], b[MAXN], c[MAXN];
priority_queue<int> Q1, Q2, Q3;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    cin >> n >> T >> k;
    for (int i = 1; i <= n; i++)
    {
        scan_d(a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        scan_d(b[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        scan_d(c[i]);
    }

    ll sum1 = 0, sum2 = 0;
    int ans = -1;
    for (int i = 1; i <= n; i++)
    {
        if (c[i])
        {
            Q1.push(b[i]);
            sum1 += b[i];
            if (Q1.size() > k)
            {
                Q2.push(Q1.top());
                sum2 += Q1.top();
                sum1 -= Q1.top();
                Q1.pop();
            }
        }
        else
        {
            Q2.push(b[i]);
            sum2 += b[i];
        }

        if (Q1.size() < k)
        {
            continue;
        }
        if (sum1 + a[i] > T)
        {
            continue;
        }

        ll temp = T - sum1 - a[i];
        // 如果 Q3 中最小花费小于 Q2 中最大花费，交换
        while (!Q3.empty() && !Q2.empty() && -Q3.top() < Q2.top())
        {
            int tag = Q2.top();
            sum2 -= Q2.top();   // 去掉 Q2 最大花费
            sum2 -= Q3.top();   // 加上 Q3 最小花费
            Q2.pop();
            Q2.push(-Q3.top());
            Q3.pop();
            Q3.push(-tag);
        }
        // 超限，去除
        while (!Q2.empty() && temp < sum2)
        {
            Q3.push(-Q2.top());
            sum2 -= Q2.top();
            Q2.pop();
        }
        // 加上 Q3 中最小依然合法，添加
        while (!Q3.empty() && temp >= sum2 - Q3.top())
        {
            Q2.push(-Q3.top());
            sum2 -= Q3.top();   // 加上 Q3 最小花费
            Q3.pop();
        }

        if (temp >= sum2 && k + (int)Q2.size() > ans)
        {
            ans = k + (int)Q2.size();
        }
    }

    cout << ans << endl;

    return 0;
}