华为OD-D卷数的分解

给定一个正整数n，如果能够分解为m(m > 1)个连续正整数之和，请输出所有分解中，m最小的分解。

如果给定整数无法分解为连续正整数，则输出字符串"N"。

输入描述:

输入数据为一整数，范围为（1, 2^30]

输出描述:

比如输入为：

21

输出：

21=10+11

备注:

21可以分解的连续正整数组合的形式有多种

21=1+2+3+4+5+6

21=6+7+8

21=10+11

输出，21=10+11，是最短的分解序列。

题目解析：如果是奇数就很简单，一定能找到相邻的两个数相加为 n,那么剩下的数该怎么处理呢？

因为要找到连续的正整数，而且m最小，那么即使有多种分解方法，在这个m里面的分解数里一定存在所有分解方法中最大的数，例如15可以分为（1+2+3+4+5），或者（4+5+6)，那么我们找的结果中包含m中会存在这个最大的6。

这样就好办了，我们只需要从15/2->1开始算，这个最大的数是多少，不断的去试，7可以吗，要保证连续7+6=13<15，再加,7+6+5>18,显然不行。

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前后都可以取元素，方便Deque<Integer> 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();}}}// 不能拆解输出"N"if(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());}
}