Backward Digit Sums(POJ-3187)题解

Myth丶恋晨 2022-12-28 07:28 143阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  Input
     *  Output
     *  Sample Input
     *  Sample Output
     *  Hint
     *  算法分析
     *  解题标程
     *  错题分析

--------------------

# 题目描述 #

FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N = 4) might go like this:

3   1   2   4
    
      4   3   6
    
        7   9
    
         16

Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

## Input ##

> Line 1: Two space-separated integers: N and the final sum.

## Output ##

> Line 1: An ordering of the integers 1…N that leads to the given sum. If there are multiple solutions, choose the one that is lexicographically least, i.e., that puts smaller numbers first.

## Sample Input ##

4 16

## Sample Output ##

3 1 2 4

## Hint ##

> Explanation of the sample:  
> There are other possible sequences, such as 3 2 1 4, but 3 1 2 4 is the lexicographically smallest.

## 算法分析 ##

*  这道题目就是一个**全排列**加**杨辉三角**
 *  全排列很好看出来
 *  杨辉三角的原因：

> 例如：4 16 -> 3 1 2 4  
> 3\*1+1\*3+1\*3+4\*1=16（1 3 3 1）  
> 就是杨辉三角的第四行的内容  
> 再如 5 56 -> 1 2 4 5 3  
> 1\*1+2\*4+4\*6+5\*4+3\*1=56(1 4 6 4 1)

**全排列可以用stl中的next\_permutation(term,term+n)来遍历全排列，这个函数的时间复杂度为O(n)，这道题如果用深搜会超时！**

## 解题标程 ##

#include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int n,ed;
    int a[100];
    int b[100];
    
    int main()
    {
        
        cin >> n >> ed;
        
        for(int i=0;i<n;i++)
            a[i]=i+1;
        
        do{
        
            for(int i=0;i<n;i++)
                b[i]=a[i];
            
            for(int i=n-1;i>0;i--)
                for(int j=0;j<i;j++)
                    b[j]=b[j]+b[j+1];
            
            if(b[0]==ed){
        
              for(int i=0;i<n;i++){
        
                cout << a[i];
                if(i!=n-1)
                    cout << " ";
              }
              cout << endl;
              break;
            }
                
        }while(next_permutation(a, a+n));
    
        return 0;
    }

--------------------

## 错题分析 ##

*  善于使用STL中的next\_permutation()函数来进行全排列。
 *  next\_permutation()实现全排列时，是直接改变数字在数组中的排序顺序。
 *  当全部排列遍历完毕后会返回false