解题思路

• 本题是一个典型的可行性判定 + 贪心构造问题。 记每个元素必须在区间 $[l,r]$ 内，数组长度为 $n$，目标总和为 $m$。

• 可行性判定：数组元素之和的最小/最大可能值分别为

  $$S_{\min}=n\cdot l,\quad S_{\max}=n\cdot r.$$

  只有当 $S_{\min}\le m\le S_{\max}$ 时才有解，否则无解（输出 $r+1$）。

• 构造算法（贪心）：

  1. 先令所有元素为 $l$，此时总和为 $S_{\min}$，剩余需要补到 $m$ 的量为 $\text{rem}=m-S_{\min}$（此时 $\text{rem}\ge 0$）。
  2. 从前到后依次把每个元素在不超过上界 $r$ 的前提下尽量增大：对第 $i$ 个元素，最多还能增加 $(r-l)$，实际增加 $\text{add}=\min(\text{rem},\, r-l)$，更新元素并减少 $\text{rem}$。
  3. 遍历结束 $\text{rem}$ 一定为 0，得到任意一组可行解。

• 该贪心等价于把“剩余增量”平均地、但不强求完全平均地往各位置“倒水”，保证区间约束并满足总和。

复杂度分析

• 单组构造只需一次线性遍历并输出：时间复杂度 $O(n)$。所有测试的 $n$ 之和不超过 $2\times 10^5$，总体可承受。
• 仅用到当前行的增量与输出数组：空间复杂度 $O(n)$（若边构造边输出，也可视为 $O(1)$ 额外空间）。

代码实现

Python

import sys

# 外部函数：根据 n, m, l, r 构造解；若无解返回 None
def build_array(n: int, m: int, l: int, r: int):
    smin = n * l
    smax = n * r
    if m < smin or m > smax:
        return None  # 无解
    a = [l] * n  # 先全置为下界
    rem = m - smin
    if rem == 0:
        return a
    cap = r - l  # 每个位置最多还能增加的量
    for i in range(n):
        if rem == 0:
            break
        add = cap if rem >= cap else rem  # 本位能加的增量
        a[i] += add
        rem -= add
    return a  # 此时 rem 必为 0

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    out_lines = []
    for _ in range(t):
        n = int(data[idx]); m = int(data[idx+1]); l = int(data[idx+2]); r = int(data[idx+3])
        idx += 4
        ans = build_array(n, m, l, r)
        if ans is None:
            out_lines.append(str(r + 1))  # 无解输出 r+1
        else:
            out_lines.append(' '.join(map(str, ans)))  # 输出任意一种可行解
    sys.stdout.write('\n'.join(out_lines))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    // 外部函数：构造解，若无解返回 null
    public static long[] buildArray(int n, long m, long l, long r) {
        long smin = (long) n * l;
        long smax = (long) n * r;
        if (m < smin || m > smax) return null; // 无解

        long[] a = new long[n];
        Arrays.fill(a, l); // 先全置为下界
        long rem = m - smin;
        if (rem == 0) return a;

        long cap = r - l; // 每个位置最多还能增加的量
        for (int i = 0; i < n && rem > 0; i++) {
            long add = Math.min(rem, cap);
            a[i] += add;
            rem -= add;
        }
        return a; // 此时 rem 必为 0
    }

    public static void main(String[] args) {
        // 数据范围不大，使用 Scanner 即可
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) {
            sc.close();
            return;
        }
        int T = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            int n = sc.nextInt();
            long m = sc.nextLong();
            long l = sc.nextLong();
            long r = sc.nextLong();

            long[] ans = buildArray(n, m, l, r);
            if (ans == null) {
                sb.append(r + 1).append('\n'); // 无解输出 r+1
            } else {
                for (int i = 0; i < n; i++) {
                    if (i > 0) sb.append(' ');
                    sb.append(ans[i]);
                }
                sb.append('\n');
            }
        }
        System.out.print(sb.toString());
        sc.close();
    }
}

C++

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

// 外部函数：构造解；若无解返回空向量（用 size==0 表示）
vector<long long> buildArray(int n, long long m, long long l, long long r) {
    long long smin = 1LL * n * l;
    long long smax = 1LL * n * r;
    if (m < smin || m > smax) return {}; // 无解

    vector<long long> a(n, l); // 先全置为下界
    long long rem = m - smin;
    if (rem == 0) return a;

    long long cap = r - l; // 每个位置最多还能增加的量
    for (int i = 0; i < n && rem > 0; ++i) {
        long long add = min(rem, cap);
        a[i] += add;
        rem -= add;
    }
    return a; // 此时 rem 必为 0
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        long long m, l, r;
        cin >> n >> m >> l >> r;

        vector<long long> ans = buildArray(n, m, l, r);
        if (ans.empty()) {
            cout << (r + 1) << '\n'; // 无解输出 r+1
        } else {
            for (int i = 0; i < n; ++i) {
                if (i) cout << ' ';
                cout << ans[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

题目内容

Tk 从小就对数字非常感兴趣，Tk 希望构造一个长度为 $n$ 的整数数组 $a$，满足所有元素的和为 $m$ ，且每个元素都在区间 $[l,r]$ 之间。

然而，Tk 并不会具体构造，于是找到了聪明的你，需要你输出任意一种满足条件的数组如果无解，则输出 $r+1$ 。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1≤ T ≤ 10^4)$，代表测试组数；

此后每组测试教据描述如下：

在一行上输入四个整数 $n,m,l,r(1≦n≦2×10^5;-10^9≦m≦10^9;-10^9≦l≦r≦10^9)$ 。

此外，保证单个测试文件中所有 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出 $n$ 个整数表示满足条件的数组；如果无解，输出 $r+1$ 。

样例1

输入

2
3 6 1 3
2 100 0 10

输出

2 2 2
11