card card card

【2017 ACM/ICPC Asia Regional Shenyang Online】card card card

【循环置尾问题】

Solution:

这道题的关键在于时间消耗,由于循环放到末尾,所以不妨在读取时便复制一份,开一个二倍的数组,而节省时间的关键在于:不要针对每一个为起点进行一次判断,而是直接从这个二倍数组从头到尾遍历一次,每遇到一次penalty为负数导致游戏结束的情况就进行一次初始化,从下一个位置接着来。这么做可以的原因十分简单,可以这样想:如果从第三张牌开始摸到第六张是最大的情况,那么我们不需要再开一次从第四张、第五章、第六张的尝试,因为它们不可能比上面那种情况更优。

另外,采取了一个“哨兵”技巧,即在二倍数组的最后放一个很大的惩罚值,这样是为了避免出现当读取到最后一个牌堆的时候Penalty还是正值而导致这一种情况没有被考虑入可能的答案中。【备注:由于在n*2位置处加上了“哨兵”,我们应当将循环条件设置成i <= n * 2】

#include <iostream>

using namespace std;

const int LIM = 1e6 + 10;
int arr[LIM * 2];
int penal[LIM * 2];

int main(void) {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            scanf("%d", arr + i);
            arr[i + n] = arr[i];
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", penal + i);
            penal[i + n] = penal[i];
        }
        penal[n * 2] = 1e7;
        arr[n * 2] = 0;
        int ans, tp = 0, ti = 0, ts = 0, maxi = 0;
        for (int i = 0; i <= 2 * n; i++) {
            ti += arr[i];
            tp += arr[i] - penal[i];
            if (tp < 0) {
                if (ti > maxi) {
                    maxi = ti;
                    ans = ts;
                }
                tp = ti = 0;
                ts = i + 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}