「BZOJ 2802」[Poi2012]Warehouse Store

#2802. [Poi2012]Warehouse Store

题目描述

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

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

输入输出格式

输入格式:

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

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

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

输出格式:

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

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

题解

贪心入门题

直接模拟题意,把顾客扔进大根堆里

然后遇到不能选的就与堆顶比较,如果更优就把堆顶的顾客扔掉,换成当前的顾客

因为没开 long long 挂了几发....

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

#define int long long

const int MAXN = 250000 + 100;

struct Node {
int in, out;
};

int n;
Node v[MAXN];

struct t {
int day, cost;
t(int _d, int _c) : day(_d) , cost(_c) {}
};

signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &v[i].in);
for (int i = 1; i <= n; i++) scanf("%d", &v[i].out);

auto cmp = [](const t &a, const t &b) -> bool {
return a.cost < b.cost;
};

int res = 0;
std::priority_queue<t, std::vector<t>, decltype(cmp)> q(cmp);
for (int i = 1; i <= n; i++) {
Node now = v[i];
res += now.in;
if (res >= now.out) {
res -= now.out;
q.push(t(i, now.out));
} else {
if (q.empty()) continue;
t replace = q.top();
if (replace.cost > now.out) {
res += replace.cost - now.out;
q.pop();
q.push(t(i, now.out));
}
}
}

std::vector<int> ans;
while (!q.empty()) ans.push_back(q.top().day), q.pop();
std::sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (auto i : ans) printf("%d ", i);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!