题解：P12836 [蓝桥杯 2025 国 B] 翻倍

linhanmo · 2025-06-20 12:53:54 · 题解

题解：P12836 [蓝桥杯 2025 国 B] 翻倍

三倍经验……

部分分

暴力翻倍每一个数字，时间复杂度 O(n)。

但是翻倍后的数字是存不下的，所以这并不能 AC。

正解

既然翻倍后的数字存不下，考虑存翻了几倍。

这样只要相邻两个数计算前一个数没翻倍时要后一个数要翻几倍加上前一个数翻了几倍即可。

显然是存得下的，时间复杂度 O(n)。

#include <stdio.h>
#include <math.h>
unsigned n;
unsigned long long ans; // 不开 long long 见祖宗
int main(void) {
    scanf("%u", &n);
    for (unsigned a, la = 0, // 边读入边计算
        d = 0 /* 累加翻了几倍 */, 
        i = 1; i <= n; la = a, ++i)
        scanf("%u", &a),
        ans += d = fmax(d + ceil(log2(1. * la / a)), 0.);
    printf("%llu", ans);
    return 0;
}