Skip to content

CF2040B Paint a Strip

原题链接：B. Paint a Strip

Tag：贪心

题目描述

您有一个长度为 \(n\) 的初始值全为 \(0\) 的 \(a_1, a_2, \ldots, a_n\) 数组。

您可以对它进行两种操作：

  1. 选择 \(i\) 这样的索引 \(1 \le i \le n\) 和 \(a_i = 0\) ，并将 \(1\) 赋值给 \(a_i\) ；
  2. 选择一对索引 \(l\) 和 \(r\) ，使得 \(1 \le l \le r \le n\) ， \(a_l = 1\) ， \(a_r = 1\) ， \(a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil\) ， 并将所有 \(l \le i \le r\) 的 \(1\) 赋值给 \(a_i\) 。

要使数组中的所有元素都等于 1，至少需要进行多少次第一类操作？

数据说明：

\(1 \leq n \leq 10^5\)

分析

直接考虑一个无限长度的数组， 根据第二个操作可以想到， 我们最优的方案一定是先把最左面的一个数字变成 \(1\)， 之后使用操作一在右边的某个位置变一个 \(1\) 出来， 再用操作二把这一个区间中的所有 \(0\) 变成 \(1\)。

根据上述的分析，我们发现每次 \(1\) 的个数最多可以变成 \((x+1)\times 2\)。 所以我们维护一个 \(x\)，初始为 \(1\)，每次操作加一乘二， 直到 \(x \geq n\)。

值得注意的是，我们一开始需要使用一个操作把最左边的数字变成 \(1\)， 所以 \(ans\) 初始化为 \(1\)，

代码实现

void NeverSayNever() {
    int n; cin >> n;
    int x = 1;
    int ans = 1;
    while(x < n){
        x = (x + 1) * 2;
        ans++;
    }
    cout << ans << endl;
}

日志

本页面创建于 2024/6/23 22:22