AtCoder
AtCoder

原题

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_c

思路

针对灯泡进行每一次操作时,可以利用差分数组来记录每一个灯泡的光照范围(intensity),然后计算出差分数组的前缀和数组即为每一次操作后的状态。

这里面比较巧妙的地方是,通过观察法(目前还没搞懂如何去证明)可以看出最多执行 O(log N) 次即可将所有灯泡的光照强度值置为最大值。所以,题目中的 K 可以缩小到 2 倍左右的 log N,最多 41 次操作。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int accum[N], bulbs[N], n, k;
int main() {
    cin >> n >> k;
    k = min(41, k);
    for (int i = 1; i <= n; ++i) cin >> bulbs[i];
    while (k--) {
        memset(accum, 0, sizeof accum);
        for (int i = 1; i <= n; ++i) {
            int l = max(1, i - bulbs[i]);
            int r = min(n, i + bulbs[i]);
            accum[l]++;
            accum[r + 1]--;
        }
        for (int i = 1; i <= n; ++i) {
            accum[i] += accum[i - 1];
        }
        memcpy(bulbs, accum, sizeof accum);
    }
    for (int i = 1; i <= n; ++i) {
        cout << bulbs[i] << " ";
    }
    return 0;
}

参考

[1] AtCoder. C Lamps

本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/c-lamps-of-tokio-marine-nichido-fire-insurance-programming-contest-2020/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。