洛谷P3545 [POI2012] HUR-Warehouse Store 题解

题目链接：P3545 [POI2012] HUR-Warehouse Store

题意：

现在有 $n$ 天。第 $i$ 天上午会进货 $A_i$ 件商品，中午的时候会有顾客需要购买 $B_i$ 件商品，可以选择满足顾客的要求，或是无视掉他。

如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。

输入格式：

第一行包含一个整数 $n$，表示有 $n$ 天。

第二行有 $n$ 个整数 $a_i$，表示第 $i$ 天上午进货 $a$ 件商品。

第三行包含 $n$ 个整数 $b_i$，表示在第 $i$ 天中午有顾客来买 $b$ 件商品。

输出格式：

第一行一个整数，表示最多能满足几天中顾客的需求。

第二行输出满足这么哪些天顾客的需求。

数据范围：

$1\le n\le 2.5\times 10^5,~0\le a_i,b_i \le 10^9$。

考虑反悔贪心。每次直接选 $b_i$ 。

如果发现库存不够了，就从之前选过的 $b$ 中取最大的，

撤销选择它，重复直到库存非负，这题就做完了。

输出方案的话可以跑两遍，第二遍的时候再记录。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(3e5 + 15))

bool used[N]; 
int n, cnt, res, a[N], b[N]; ll sum;
struct node { int x, id; };
bool operator<(node x, node y) { return x.x < y.x; }
priority_queue<node> q;
void print() { rep(i, 1, n) if(used[i]) cout << i << ' '; exit(0); }
void solve(const int tmp)
{
    sum = 0, cnt = 0, res = 0; q = {};
    rep(i, 1, n)
    {
        sum += a[i]; q.push({b[i], i}); ++cnt; sum -= b[i];
        if(!~tmp) used[i] = true; 
        while(!q.empty() && sum < 0)
        {
            auto [x, y] = q.top(); q.pop();
            --cnt; sum += x; if(!~tmp) used[y] = false;
        }
        if(!~tmp) up(res, cnt); else if(cnt == tmp) print();
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) cin >> b[i];
    solve(-1); cout << res << '\n'; solve(res);
    return 0;
}