$数列$数列

题目描述见链接 .

$正解部分$正解部分

首先考虑怎么划分序列,
可以想到: 最优划分方法 会将 序列 分为连续的几段 上升序列 .

若存在下降序列, 可以将其倒置, 答案会更优 .

设划分了 $cnt$cnt 段 上升序列, 则 显然 $ans=N-cnt$ans=N−cnt,

现在要使得 $ans$ans 尽可能大, 就要使得 $cnt$cnt 尽量小,

考虑 $cnt$cnt 受什么限制, 受 $M$M 的大小限制,
$具体来说$具体来说: 设每个 上升序列 的长度为 $x_i$xi​, 则受到的限制为 $sum=\sum \frac{(1+x_i)x_i}{2}\le M$sum=∑2(1+xi​)xi​​≤M .

此时可以想到, 若 $cnt$cnt 可以合法地构造, 那么 $cnt+1$cnt+1 也一定可以合法地构造, 换句话说, $cnt$cnt 具有单调性 .

将 $cnt$cnt 段 上升序列 中的一段上升序列分割为两个, $sum$sum 只会更小, 所以不会不合法 .

于是 二分答案, 二分 $cnt$cnt, 考虑如何 $check\left(\right)$check(),

$sum$sum 最小都大于 $M$M 时, 说明 $cnt$cnt 一定不合法, 依此进行判断,

考虑 $cnt$cnt 固定的时候, $sum$sum 什么时候最小, 显然当每个 $x_i$xi​ 都尽可能均匀时, $sum$sum 最小 .

设最大的 $x_i$xi​ 为 $x_{max}$xmax​, 最小的 $x_i$xi​ 为 $x_{min}$xmin​, 则当把 $x_{max}$xmax​长度 减 $1$1, 把 $x_{min}$xmin​ 长度 加 $1$1,
$sum$sum 的变化值为 $-x_{max}+(x_{min}+1)$−xmax​+(xmin​+1), 其中 $x_{min}+1\le x_{max}$xmin​+1≤xmax​, 所以这么操作 $sum$sum 不会更大 .

于是对每个 $x_i$xi​ 赋初值 $\frac{N}{cnt}$cntN​, 剩下 $N\%i$N%i 均匀散布到前面 $cnt$cnt 个长度为 $\frac{N}{cnt}$cntN​ 个 $x_i$xi​ 中,
得到 $x_i$xi​, 计算 $sum$sum, 判断是否小于等于 $M$M 即可 .

时间复杂度 $O(\log n+n)$O(logn+n)

$实现部分$实现部分

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 1e5 + 5;

int N;
int M;
int min_cnt;

bool chk(int cnt){
        int x_1 = N/cnt, x_2 = N/cnt + 1;
        int num_1 = cnt - N%cnt, num_2 = N%cnt;
        ll s = (1ll+x_1)*x_1/2*num_1 + (1ll+x_2)*x_2/2*num_2;
        return s <= 1ll*M;
}

int main(){
        scanf("%d%d", &N, &M);
        int l = 1, r = N; min_cnt = N;
        while(l <= r){
                int mid = l+r >> 1;
                if(chk(mid)) min_cnt = std::min(mid, min_cnt), r = mid - 1;
                else l = mid + 1;
        }
        int x_1 = N/min_cnt, x_2 = N/min_cnt + 1;
        int num_1 = min_cnt - N%min_cnt, num_2 = N%min_cnt;
        for(reg int i = 1; i <= num_1; i ++)
                for(reg int j = 1; j <= x_1; j ++) printf("%d ", j);
        for(reg int i = 1; i <= num_2; i ++)
                for(reg int j = 1; j <= x_2; j ++) printf("%d ", j);
        return 0;
}