题解 | #andy的树被砍了#

我来一个C语言的题解

#include <stdio.h> #include <stdlib.h>

int main() { int n; scanf("%d", &n);

int* h = (int*)malloc(n * sizeof(int));
int* c = (int*)malloc(n * sizeof(int));
int* d = (int*)malloc(n * sizeof(int));

// 读取输入
for (int i = 0; i < n; i++) {
    scanf("%d", &h[i]);
}
for (int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
}

// 前缀和数组，prefix_sum[i]表示前i+1天的砍伐量之和
long long* prefix_sum = (long long*)malloc((n + 1) * sizeof(long long));
prefix_sum[0] = 0;
for (int i = 1; i <= n; i++) {
    prefix_sum[i] = prefix_sum[i - 1] + c[i - 1];
}

// 对于每棵树，二分查找死亡天数
for (int i = 0; i < n; i++) {
    int left = i, right = n - 1;
    int death_day = n + 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 计算从第i天到第mid天的累计砍伐量
        long long total_cut = prefix_sum[mid + 1] - prefix_sum[i];

        if (total_cut >= h[i]) {
            death_day = mid + 1;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }

    d[i] = death_day;
}

// 输出结果
for (int i = 0; i < n; i++) {
    printf("%d ", d[i]);
}
printf("\n");

free(h);
free(c);
free(d);
free(prefix_sum);//注意free

return 0;

}