整数划分

NC252724. 整数划分

描述

牛牛有一个整数 $n$ ，他想知道这个数字所有好的划分中字典序最小的划分方案是什么。

一个好的划分是一个正整数序列，序列中所有数字的和等于 $n$ ，且序列中不存在相同的数。

输入描述

本题采用多组案例输入，第一行一个整数 $T$ 代表案例组数。

每组案例中，输入一行一个整数代表 $n$ 。

保证： $0 < n \le 10^6$ 单个测试点中所有案例 $n$ 的和不超过 $10^6$

输出描述

对于每组案例，输出一行若干个正整数代表划分出字典序最小的序列，整数之间用空格分隔。

示例1

输入:

输出:

1 3
1 2 4
1 2 3 4

上次编辑到这里，代码来自缓存点击恢复默认模板

Go 解法, 执行用时: 469ms, 内存消耗: 4128K, 提交时间: 2023-08-13 13:47:02

package main

import (
	"fmt"
)

func main() {
	var t int
	fmt.Scan(&t)
	for t>0 {
		t--
		var n int
		var x int =1
		fmt.Scan(&n)
		for n>0 {
			if n-x <= x {
				fmt.Printf("%d\n",n)
				break
			}
			fmt.Printf("%d ",x)
			n -= x
			x++
		}
	}
}

Python3 解法, 执行用时: 1006ms, 内存消耗: 4936K, 提交时间: 2023-08-13 13:46:40

for ii in range(int(input())):
    n=int(input())
    i=1
    k=[]
    while n>=i:
        k.append(i)
        n=n-i
        i=i+1
    if n>0:
        k[-1]=k[-1]+n
    print(*k)