最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界聚焦：Codeforces Round 876 (Div. 2)题解

来源：博客园


(相关资料图)

Codeforces Round 876 (Div. 2)

A. The Good Array

标签

greedymath

题意

对于任意 \(i\in\{1,2,\dots,n\}\)，要求数列 \(a\) 满足前 \(i\) 个元素中至少有 \(\lceil\frac{i}{k}\rceil\) 个元素为 \(1\)，后 \(i\) 个元素中至少有 \(\lceil\frac{i}{k}\rceil\) 个元素为 \(1\)。

思路

  1. 考虑特殊情况 \(k=1\)，因为此时序列 \(1\) 的插入点连续，所以答案为 \(n\)。
  2. 欲令数列 \(a\) 满足前 \(i\) 个元素中至少有 \(\lceil\frac{i}{k}\rceil\) 个元素为 \(1\)，根据贪心只需要在 \(1, k+1, 2k+1, \dots,xk+1,n\) 的位置插入 \(1\)。在该前提下，讨论欲满足另一要求需要额外插入的 \(1\) 的个数，分类讨论。
  3. 若 \(xk+1\) 与 \(n\) 之间的差值 \(d=n\%k-1> 0\)，则易得 \(0

代码

点击查看代码
#include #define ll long long#define ld long double#define ull unsigned long longusing namespace std;int t, n, k; int main (){scanf ("%d", &t);while (t --) {scanf ("%d %d",&n, &k);if (k == 1) printf ("%d\n", n);else if (n % k - 1 != 0) printf ("%d\n", (n - 1) / k + 2);else printf ("%d\n", (n - 1) / k + 1);}return 0;}

收获

  1. 脑子混乱时，静下心来重新发现性质。比如，该题最关键的性质为除去位置 1 和位置 n 处的 \(1\)，其他位置的 \(1\) 之间的差值恒为 \(k\)，以及对是否需要额外插 \(1\) 的判断条件。

关键词：