题解：CF416D Population Size

· · 题解

前言：

本题所需的前置知识：几乎是 0。

本题的思维含量：114514。

本题的代码难度：1919810。

大体思路：

有一个简单的贪心结论：一个数能归入前面的等差数列，就不要归入后面的。

对于一个等差数列，其开头被拿走了不会有任何问题，其仍然为一个等差数列，公差也不变，所以前面的贪心结论是对的。

知周所众，等差数列要想确定下来，至少需要两个确定的数字，这样我们才可以求出公差。

因此，我们应该利用指针去跑一遍，分别找出最先两个相邻确定的数，这样就可以初步确定等差数列了。

我们通过确定的两个数字，可以求出公差，公差不难求，我们知道这一串中有多少个数字，同样就能知道间隔数，因此公差为两数之差与间隔数的商。

这时候我们还要考虑一个问题，也就是这个结果不一定为整数，倘若无法整除，就会导致结果有小数，这不符合题意，更不符合现实。

对于结果不为整数的情况，我们要将这两个数拆散，前面一个数字就可以与它前面以及第二个数前面的 -1 合并为一个等差数列，最好公差为 0（当然，我们知道就行，说一下只是表示这样成立）。至于第二个数，重新让指针跑起来，接着以第二个确定的数和第三个确定的数为核心，再次创造等差数列。

倘若公差为整数，我们就要开始进行另一种方向的考虑，我们让这个等差数列延伸，向前延伸。显然，人口不可能为负数，所以不论如何，向前延伸整个等差数列不可能出现负数，当向前延伸时，出现负数，则这个 -1 无法纳入等差数列，根据我们前面的贪心，能纳入前面的，就不要纳入后面的，所以此时，我们和前面的公差不为整数的情况一样处理。

倘若两个数前面的 -1 全部都可以纳入等差数列中，则我们考虑等差数列向后延伸，能跑多远跑多远。跑不动了就指针继续向后跑，然后重新开始一个这样的过程。总的来说，可以用 while 循环实现。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],ans,p=1,d;    //p 表示指针。
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(p<=n){
        ans++;
        int front,mid,val1,val2;
        front=mid=val1=val2=0;
        while(p<=n&&a[p]==-1){
            p++;
            front++;
        }       //标记第一个点。
        if(p==n+1)break;
        val1=a[p];
        p++;
        while(p<=n&&a[p]==-1){
            p++;
            mid++;
        }       //标记第二个点。
        val2=a[p];
        if(p==n+1)break;
        if((val2-val1)%(mid+1)==0)d=(val2-val1)/(mid+1);             //计算公差。
        else continue;        //公差为小数。
        if(val1-d*front<=0)continue;    //前面的 -1 无法纳入公差。
        while(p<=n){
            if(a[p+1]==-1&&a[p]+d>0){
                a[p+1]=a[p]+d;
                p++;
            }
            else if(a[p+1]==a[p]+d&&a[p]+d>0)p++;
            else break;
        }              //向后延伸。
        p++;
    }
    cout<<ans<<endl;
    return 0;
}

后话：

这道题是南京集训时听号爸讲的，号爸说这份代码是他看到 CF 上有人这么写，他感觉非常感动，认为有必要讲一下。

这道题只要会数组和循环就可以做，压根不需要高级的算法。给人一种用开水白菜做出国宴的感觉。就像《口技》中的：一人、一桌、一椅、一扇、一抚尺而已。

本题的变量有局部的也有全局的，局部变量在每一轮中都会重启更新，而全局变量是一个连续的不断跑的状态，这份程序恰恰令我们学习到了局部变量和全局变量的正确用法。

指针的运用也很巧妙。

总的来说，号爸认为，这是一道初学者也可以会的题目，但是，其对于写代码的基本功要求很高，非常适合出在联赛第一题，来检验选手会不会写代码。（话说这不是蓝题吗，这下真成 NOI plus 了）

说句闲话：虽然上课时听得似懂非懂，自己写的时候也是靠 @kongliheng AC，结果发现，自己写了篇题解，居然开智了。写题解有益学习这块。