gcj2013 B题 Manage your Energy

Posted on 五 07 十一月 2014 in 编码

最近刷codejam的略感无力，本来以为今天刷gcj2013 round1A应该能轻松耍一下。。但是被第二题卡住，看来最近确实脑残了......

这里仅仅记录下脑残的思路是如何产生，以便日后回想自己的too young too naive的时光。。

NC One

看完题目第一感觉，找出最大的Vmax然后把所有e * Vmax，其他求和 * r。但总有种不可能这么简单的感觉，但还是先写出来试试。果然码完就觉得有问题。

NC Two

反省第一版的问题后，发现在最大的值所在位置之后的一段v里需要再另外找最大值。于是求f[i]，表示i点及其后的最大值，接着从前往后扫一遍，尽量将e用在f[i]==v[i]的点上。然后就以为已经解决了。。

正解

最后还是没找出问题所在，时间不多（还有许多砖要搬），就直接看题解了。。

对于每一个i，需要找出下一个比i大的位置j，那么肯定应该尽量把e用于j位置。。至于快速找出i的下一个比i大的位置，需要用到单调栈。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;

typedef long long LL;
int a[10004], nxt[10004];
stack<int> st;

int main() {
    int T, e, r, n;
    scanf("%d", &T);
    for(int cas = 1; cas <= T; cas++) {
        scanf("%d%d%d", &e, &r, &n);
        if(r > e) r = e;
        for(int i = 0; i < n; i++)
            scanf("%d", a + i);
        for(int i = 0; i < n; i++) {
            while(!st.empty() && a[i] > a[st.top()]) {
                nxt[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty()){
            nxt[st.top()] = -1;
            st.pop();
        }
        LL ans = 0;
        int now = e;
        for(int i = 0; i < n; i++) {
            if(nxt[i] == -1 || (nxt[i] - i) * (LL)r >= e) {
                ans += now * (LL)a[i];
                now = 0;
            } else if((nxt[i] - i) * (LL)r + now > e) {
                ans += ((nxt[i] - i) * (LL)r + now - e) * (LL)a[i];
                now = e - (nxt[i] - i) * (LL)r;
            }
            now += r;
            if(now > e) now = e;
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

GCJ