牛客练习赛51 E 数列

**这道题首先可以二分答案，也就是满足条件的下标个数，我们可以换种方式来理解他：数列中出现的断层数量，下图表示的就是样例中的情况，假使数列为直接的1-n序列，那答案显然是n-1，而如果其中每出现一个断层，则答案减一，而每个断层开始自然是1最优，因此我们需要确定的就是最少的断层数**

**那么为什么具有二分性呢，很显然，一个有x个断层的序列，那对于x+1个断层，我只要在原序列中随意一个断层中再断一次就能严格减小花费，因此二分是合理的**

**然后我们的check函数中要做的就是确定构成该数目断层需要的最少数字之和，那么这里又是很容易就能想到，最长的断层和最短的断层长度差值不会超过1，为什么？**
**如下图，有一个123412的数组，那我把4去掉之后在第二个2后面加一个3，断层数不变，但是总花费减小了，所以我们发现高的断层补低的断层可以减小花费，那么不断补之后的结果就是高度差小于等于1**

**所以对于当前的断层数，我们可以通过向下取整来求得较低的断层的高度，再取余解出较高的断层个数，加减乘除一下返回最小花费：**

```cpp
bool check(int x){
    int cnt=n/(x+1);//较低的高度
    int cct=n%(cnt*(x+1));//较高断层的个数
    int num=(x+1)*s[cnt]+cct*(cnt+1);//每个较高的断层，相当于在较低的断层后加了一列cnt+1，因此乘上个数再加上
    return num<=m;//判断合理性
}
```
**找到了最小断层数以后，就可以通过之前求解的高度和两种断层的个数直接输出了：**

```cpp
void solve(int x){
    int cnt=n/(x+1);//高度
    int cct=n%(x+1);
    int pos=0;
    for(int i=1;i<=cct;i++){//cct个较高断层
    for(int j=1;j<=cnt+1;j++){
        as[++pos]=j;
    }
}
    for(int i=1;i<=x+1-cct;i++){//x+1-cct个较低断层
        for(int j=1;j<=cnt;j++){
            as[++pos]=j;
        }
    }
    for(int i=1;i<=pos;i++){
        printf("%d",as[i]);if(i!=pos)printf(" ");
    }    
}
```
## 完整代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41228594