题解：P13286 [GCJ 2013 #1A] Manage your Energy

· · 题解

Solution

题意还是比较清晰的，这里就不解释了。
由贪心思想，我们可以得出两个显然的结论：

  1. 应将更多的能量留给更高价值的活动。
  2. 出现能量浪费的方案一定不优。

那么，为了实现结论 1，我们引入一个数据结构：单调栈。 何为单调栈？顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。——引自 OI Wiki
我们这里需要的是栈顶元素最小的单调栈。为什么呢？如果当前活动价值比栈顶元素高，那么根据结论 1，我们应该把栈内比当前活动价值低元素的能量留给当前活动。于是，我们不断地弹出栈顶元素，为当前活动预留能量，直到栈顶元素的价值高于当前元素为止。这时，当前元素进栈。这样的操作维护了栈的单调性。

又因为每个活动分配的能量最多为 E，则根据结论 2，如果已经为当前活动预留了 E 的能量，我们就不需要再为它预留了。

其实在这里，我们又可以从另一个角度理解单调栈的使用了：我们总是先修改后来的（也就是价值较低的）元素，而尽量保持价值较高的元素不变。

那么，看看代码吧：

#include <iostream>
#include <stack>
#define int long long
using namespace std;
const int N = 1e4 + 5;
int T, E, R, n, v[N], e[N], ans;
stack<int> st;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    for (int tsk = 1; tsk <= T; tsk++) {
        cout << "Case #" << tsk << ": ";
        cin >> E >> R >> n;
        for (int i = 1; i <= n; i++) cin >> v[i];
        e[1] = E;
        st.push(1);
        for (int i = 2; i <= n; i++) {
            e[i] = min(E, R);
            while (!st.empty() && v[i] > v[st.top()]) {
                if (e[i] + e[st.top()] <= E) {
                    e[i] += e[st.top()];
                    e[st.top()] = 0;
                    st.pop();
                } else {
                    e[st.top()] -= E - e[i];
                    e[i] = E;
                    st.pop();
                }
            }
            st.push(i);
        }
        ans = 0;
        for (int i = 1; i <= n; i++) ans += e[i] * v[i];
        cout << ans << '\n';
    }
    return 0;
}

Thanks for your time!