思路：贪心

因为我们要使得差值的数不同的尽可能多，那么就是去考虑差值 1, 2, 3, ... 为多少。

那么 $a_1$ 必然为 $1$ ，$a_2=a_1+1$, $a_3=a_2+2, ... a_i = a_{i-1}+i$ ，直到 $a_i=a_{i-1}+i>m$ 停止。此外，你还要保证后续的每个差值都至少为 $1$ 。

所以 $a_i=a_{i-1}+i$ 需要保证：

• $a_i\leq m$
• $a_{j+1}>a_j(j\geq i)$ 且 $a_{j+1}\leq m$

贪心地从小到大增加差值，直到增加差值后 $a_i$ 及其之后的值不满足上述两个条件，则后面的差值均设置为 $1$ 即可。

时间复杂度：$O(n)$

代码

Python

n, m = map(int, input().split())
a = [1]
# 添加新的数的时候
# 假设当前需要递增 x ，当前还有 y 个数需要添加，那么需要判断 a[-1] + x + y - 1 <= m
# 如果 a[-1] + x + y - 1 > m ，则后续全部为 1 即可

x = 1
y = n - 1
while y > 0:
    if a[-1] + x + y - 1 <= m:
        a.append(a[-1] + x)
        x += 1
    else:
        a.append(a[-1] + 1)
    y -= 1
    
print(*a)

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll n,m;
    cin>>n>>m;
    
    vector<ll> A(n+1,0);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        A[i]=1+i*(i-1)/2;
    }
    for(ll i=n;i>=1;i--){
        if(m-A[i]>=n-i){
            ans = i;
            break;
        }
    }
    for(ll i=ans+1;i<=n;i++){
        A[i]=A[i-1]+1;
    }
    for(ll i=1;i<=n;i++){
        cout << A[i] <<" ";
    }


    
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int cur = 1;
        for (int i = 0; i < n; i++) {
            if (cur + i + n - i - 1 > m) {
                cur++;
                System.out.print(cur + " ");
            } else {
                cur += i;
                System.out.print(cur + " ");
            }
        }

    }
}

题目描述

小美有一个长度为 $n$ 的数组 $a$ ，下标从 $1$ 开始，这个数组满足 $a_i<a_{i+1}, (1\leq i<n)$。

通过这个数组前后元素相减，得到了一个长度为 $n-1$ 的数组 $b$ 。

$b_i=a_{i+1}-a_i (1\leq i<n)$

现在，他想让你重新构造一个新的数组 $a$ ，通过新的数组 $a$ 得到的新的数组 $b$ ，新的数组 $b$ 中不同的元素数量尽可能多。

小美对你构造出的新数组 $a$ 有如下两个要求：

• $a_i<a_{i+1}$
• $1\leq a_i\leq m$

请你输出你构造出的新的数组 $a$ ，任意一个满足要求的数组即可。

输入描述

一行，两个整数$n,m(1 \leq n \leq m \leq 10^5)$，表示数组的长度和数组元素的最大值。

输出描述

一行，$n$个整数，表示构造出的数组 $a$ ，第 $i$ 个数为 $a_i (1\leq a_i\leq m)$。

样例

输入

3 10

输出

1 5 10