C Lamps of Tokio Marine & Nichido Fire Insurance Programming Contest 2020
文章目录

  • 原题
  • 思路
  • 代码
  • 参考

原题

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

C Lamps of Tokio Marine & Nichido Fire Insurance Programming Contest 2020leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » C Lamps of Tokio Marine & Nichido Fire Insurance Programming Contest 2020leetcode刷题题解