注册公司法人年龄要求,seo公司运营,中国建筑资讯网,军事新闻俄乌最新消息给定一个正整数n#xff0c;如果能够分解为m(m 1)个连续正整数之和#xff0c;请输出所有分解中#xff0c;m最小的分解。 如果给定整数无法分解为连续正整数#xff0c;则输出字符串N。 输入描述: 输入数据为一整数#xff0c;范围为#xff08;1, 2^3… 给定一个正整数n如果能够分解为m(m 1)个连续正整数之和请输出所有分解中m最小的分解。 如果给定整数无法分解为连续正整数则输出字符串N。 输入描述: 输入数据为一整数范围为1, 2^30] 输出描述: 比如输入为 21 输出 211011 备注: 21可以分解的连续正整数组合的形式有多种 21123456 21678 211011 输出211011是最短的分解序列。 题目解析如果是奇数就很简单一定能找到相邻的两个数相加为 n,那么剩下的数该怎么处理呢
因为要找到连续的正整数而且m最小那么即使有多种分解方法在这个m里面的分解数里一定存在所有分解方法中最大的数例如15可以分为12345或者456)那么我们找的结果中包含m中会存在这个最大的6。
这样就好办了我们只需要从15/2-1开始算这个最大的数是多少不断的去试7可以吗要保证连续761315再加,76518,显然不行。
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;public class Main {public static void main(String[] args) {
// int n 10;Scanner scanner new Scanner(System.in);int n scanner.nextInt();// n 为奇数// deque前后都可以取元素方便DequeInteger deque new LinkedList();// 标识位看是否可以拆解成连续数相加boolean flag false;// n为奇数if (n % 2 1) {System.out.println(n n / 2 (n / 2 1));return;} else {// n为偶数int start n / 2;int sum 0;// 从大数开始试for (int i start; i 0; i--) {deque.add(i);sum i;if (sum n) {flag true;break;} else if (sum n) {sum - deque.peek();deque.poll();}}}// 不能拆解输出Nif(flag false){System.out.println(N);return;}// 可以的话从deque中取元素出来注意顺序System.out.print(n );while (deque.size() 1) {System.out.print(deque.pollLast());System.out.print();}System.out.println(deque.pollLast());}
}
