【题解】HackerRank - A Race Against Time

Posted on In Disqus:

题目

https://www.hackerrank.com/contests/w36/challenges/a-race-against-time/

题意

题面特别混乱。

有一列物品 \((h_i,p_i)\) 和一个初始的 \(H\)，依次从中中选出一些物品，使得代价和最小：

  • 选一个物品的代价是 \(|h_i-h_{cur}|+p_i\)。
  • 如果遇到一个 \(h_i>h_{cur}\)，那么这个数必须选。
  • 最后的总代价是所有选择的物品产生的代价和加上 \(n\)。

题解

  • 依次考虑每一个数，对于所有高度比当前小的，都必须选自己，从中挑个 \(cost - h\) 最小的。
  • 对于所有高度大于等于自己的，可以选也可以不选。如果选，为了使代价最小，那么从中挑出 \(cost + h\) 最小的。
  • 因为有要求强制选择，所以高度比当前小的都可以依次从一个单调栈中弹出并计算转移后的代价，然后用一个 set 维护栈中所有元素 \(cost+h\) 的值。最后将当前元素以最小代价入栈就好了。

代码

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>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(vector<T> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 + 100;
const LL INF = 1E18;
LL n, H;
LL h[maxn], p[maxn];
multiset<LL> all;
struct P {
    LL h, v;
};
stack<P> S;

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    cin >> n >> H; --n;
    FOR (i, 0, n) scanf("%lld", &h[i]);
    FOR (i, 0, n) scanf("%lld", &p[i]);
    S.push({H, H}); all.insert(H);
    FOR (i, 0, n) {
        LL v = INF;
        while (!S.empty() && S.top().h < h[i]) {
            P t = S.top(); S.pop();
            all.erase(all.find(t.v));
            v = min(v, h[i] - t.h + (t.v - t.h));
        }
        if (!all.empty()) v = min(v, *all.begin() - h[i]);
        v += p[i];
        S.push({h[i], v + h[i]});
        all.insert(v + h[i]);
    }
    LL ans = INF;
    while (!S.empty()) {
        P t = S.top(); S.pop();
        ans = min(ans, t.v - t.h);
    }
    cout << ans + n + 1 << endl;
}