题解：P11296 [NOISG2018 Prelim] Snail

翻译自官方题解。

如果你爆

37

分了，那么很可能是因为你枚举的时候不到位。

基本的思路是小学奥数：求出一天上滑的量，然后计算天数即可。最后一天加上去超过没加上去又没到井口的部分暴力求解即可。

注意 $P_i$ 可能为负，也就是说，你枚举时必须枚举两天的量。

感性理解：可能是

-x,x

这种操作类型。

第一天上去了

x

，第二天先回到

0

然后再到

x

。这种情况下如果

H>x

则无解。

参考代码：

CPP

#include <cstdio>
#include <algorithm>
#include <assert.h>
#define INF 1012345678012345678LL
#define BIG 1000000000000LL
using namespace std;
typedef long long ll;
ll H;
int N;
ll P[10010];
ll simulate[20010]; // 是 P_i
ll increment = 0; // increment 增量，每次增长多少
bool printed = 0;
int main(void) {
    scanf("%lld%d", &H, &N);
    assert(1<=H && H<=BIG);
    assert(1<=N && N<=10000);//防君子不防小人
    for (int i=0;i<N;i++) {
        scanf("%lld", &P[i]);
        assert(-BIG<=P[i] && P[i]<=BIG);
    }
    // **模拟 2 天**
    simulate[0] = 0;
    for (int i=0;i<2*N;i++) { // 你可能忘记它而爆 37 pts
        simulate[i+1] = max(simulate[i]+P[i%N], 0LL); // 记得取 max
        if (simulate[i+1] >= H) { // 第一次就超过了
            printf("%d %d\n", i/N, i%N);
            printed = 1;
            break;
        }
    }
    if (!printed) {
        for (int i=0;i<N;i++) {
            increment += P[i]; // 可能向下到负数
            // 如果真到了呢？
            if (increment <= -H) { // 不可能的
                printf("-1 -1\n");
                printed = true;
                break;
            }
        }
    }
    if (!printed) {
        // 每天退步一点点
        if (increment <= 0) {
            // 那就不用爬了
            printf("-1 -1\n");
            printed = true;
        } else {
            ll bestDays = INF;
            int phase = 0;
            for (int i=0;i<N;i++) {
                ll days = 1+(H-simulate[N+i+1]+increment-1)/increment;
                if (bestDays > days) {
                    bestDays = days;
                    phase = i;
                }
            }
            printf("%lld %d\n", bestDays, phase);
            printed = true;
        }
    }
    return 0;
}

题解：P11296 [NOISG2018 Prelim] Snail

文章操作

相关推荐

评论

题解：P11296 [NOISG2018 Prelim] Snail