CF416D 题解

AlanCRL · 2023-08-09 22:20:33 · 题解

CF416D 题解

题目大意

给你一个 n 个数的序列，序列中的 -1 可以被视为是任何数，需要构造几段等差数列（且数列内的数都要是正整数）。并最小化段数并输出。

题解

分析

这道题并没有想象中那么难。我的代码是一个简单的贪心，复杂度是 O(n)。需要注意一些细节（见文末）。

主体思路：通过 2 个数计算公差，判断数的同时考虑 -1。
我们就从一个样例入手吧。

输入

9
-1 6 -1 2 -1 4 7 -1 2

输出

3

其中一种可行的方案：8 6 4 2 1 4 7 10 2 这个例子我们一共分成 3 段。

• 8 6 4 2
• 1 4 7 10
• 2

学习详细思路

初始变量：

int g = 0x7fffffffffffffff; //公差，初值是极大值
int last = -1; //上一个不为 -1 的数的位置
int cnt = 0; //统计两个数中间有多少个 -1
int idx = 0; //统计每段前有多少 -1

我们开始模拟程序进入循环：

第一段：

• 当 i = 1, a_i = -1 时：idx++ 统计每段前的 -1 个数，后面有大作用。

• 当 i = 2, a_i = 6 时：last = 2 记录不为 -1 数的位置，后续用于计算公差。

• 当 i = 3, a_i = -1 时：cnt++ 记录两个数之间 -1 的个数（用于计算公差）。

• 当 i = 4, a_i = 2 时：现在有 2 个数了，已经可以计算公差：(a[i] - a[last]) / (cnt + 1)。 此时 a[i] 为 2，a[last] 为 6。
  通过他们的差值，然后除以 cnt + 1 ，加一是因为 i 个数间有 i+1 个间隔，这样我们就得出公差是 -2 即每次减二，方差为整数。

  我们先不着急继续往后看，因为前面还有一个 -1 没有考虑：

  if (idx)
  {
      if (a[last] - idx * g <= 0)
      {
          ans++;
          i--; //从当前位置开始下一段，先-- 因为 continue 会++
          last = -1, cnt = 0, idx = 0, g = 0x7fffffffffffffff;
          continue;
      }
      idx = 0;
  }

  如果段首存在 -1，则判断按照公差前面的值会不会小于等于 0。如果小于等于 0，则结束本段，并开启下一段并重置变量。

• 当 i = 5, a_i = -1 时：按照公差现在已经小于等于 0 了，需要重新开启一段并重置变量。

第二段

• 当 i = 5, a_i = -1 时：再次从 -1 开始，并 idx++。
• 当 i = 6, a_i = 4 时：一个数不能计算公差，先让 last 记录位置（防止接下来是 -1）。
• 当 i = 7, a_i = 7 时：两个数直接计算公差：a[i] - a[last] 是 3。
  同时验证段首的 -1 是 1 大于 0 符合条件无需多开一段。
• 当 i = 8, a_i = -1 时：按照公差计算，我们直接可以将其替换成 10，但需要判断是否大于 0 否则又必须开启新的一段。
• 当 i = 9, a_i = 2 时：公差已经不符合了，现在需要开启新的一段并重置变量。
• 当 i = 9, a_i = 2 时：再次来到 2，只有一个数自己是一个数列。

代码

为了防止抄袭，删去了一些不重要的内容。

#define int long long //需要开 long long

const int N = 2e5 + 5;

int n, ans = 1;
int a[N];

signed main()
{
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);

    int g = 0x7fffffffffffffff; //公差，初值是极大值
    int last = -1; //上一个正整数的位置
    int cnt = 0; //统计两个数中间有多少个 -1
    int idx = 0; //统计每段前有多少 -1

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == -1) //当前数是 -1
        {
            if (last == -1) //首段开始是 -1
            {
                idx++;
                continue;
            }

            if (g != 0x7fffffffffffffff) //已经计算出公差了，需要判断 -1 是否符合条件
            {
                a[i] = a[last] + g, last = i; //直接改变其值，使连续的 -1 可以直接计算

                if (a[i] <= 0) //不符合条件，重新开始一段
                {
                    ans++;
                    a[i] = -1;
                    last = -1, cnt = 0, g = 0x7fffffffffffffff;
                    i--;
                    continue;
                }
            }
            else cnt++;
        }
        else
        {
            if (last == -1) //如果上一个正整数没有记录，说明目前是本段中第一个正整数，记录并跳过
            {
                last = i;
                continue;
            }

            if (g == 0x7fffffffffffffff) //计算公差
            {
                if (cnt) //两正整数间存在-1
                {
                    long double tmp = a[i] - a[last];
                    tmp /= cnt + 1;

                    if (tmp != (int)tmp)
                    {
                        ans++;
                        last = -1, cnt = 0, idx = 0, g = 0x7fffffffffffffff;
                        i--;
                        continue;
                    }
                    else g = tmp;

                    cnt = 0;
                }
                else g = a[i] - a[last]; //两正整数相邻求公差

                if (idx) //段首存在 -1
                {
                    if (a[last] - idx * g <= 0) //不能满足重开一段
                    {
                        ans++;
                        i--;
                        last = -1, cnt = 0, idx = 0, g = 0x7fffffffffffffff;
                        continue;
                    }
                    idx = 0;
                }
            }
            else //存在公差
            {
                if (a[i] - a[last] != g)  //判断下个数是否满足条件
                {
                    ans++;
                    last = -1, cnt = 0, g = 0x7fffffffffffffff;
                    i--;
                    continue;
                }
            }
            last = i;
        }
    }

    write(ans);

    return 0;
}

提示

以下是一些特殊样例，看看你考虑到了吗？

• 3 2 1 -1 -1 -1 -1 1 2 3 3：注意判断 -1 处填入值是否在正整数范围内。
• -1 1 7 -1 5 2 可以是 1 1 7 6 5。
• -1 -1 2 -1 -1 -1 5 9 2：可以是 2 2 2 2 2 5 9 注意考虑 -1。

好了，题解到此结束！觉得写的不错点个赞再走吧！有疑问请联系我。