題目：
給你10分鐘時(shí)間腾它，根據(jù)上排給出十個(gè)數(shù)宅静，在其下排填出對應(yīng)的十個(gè)數(shù)痰催。要求下排每個(gè)數(shù)都是先前上排對應(yīng)那個(gè)數(shù)在下排十個(gè)數(shù)中出現(xiàn)的次數(shù)姻报。
舉一個(gè)例子己英，
數(shù)值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
難點(diǎn)：理解題意，然后從中找出規(guī)則
思路：理解下排中的每個(gè)數(shù)都是上排對應(yīng)數(shù)字在下排的出現(xiàn)次數(shù)
假設(shè)上排a[0]~a[n-1]
下排b[0]~b[n-1]
不難看出會有如下規(guī)則：
設(shè)上排的數(shù)字用 a[i]表示, 下排的數(shù)字用b[i]表示吴旋，每排有n個(gè)數(shù)字损肛。則應(yīng)滿足條件：
① ∑b[i] = n 下排所有數(shù)字的和為n
②∑a[i]b[i] = n 上下排對應(yīng)的數(shù)字乘積相加的和為n
③ 下排出現(xiàn)了 b[i] 個(gè) a[i]
④b[i] 一定小于 n
方法是暴力查找，從全0開始 嘗試所有的0-n的數(shù)字組合
在每次選擇一個(gè)數(shù)字后荣瑟，先用∑a[i]b[i] <= n 和 ∑b[i] <= n 的條件去掉一大部分不符合條件的 相當(dāng)于截枝 加快速度
然后對每次選定所有下排的數(shù)后治拿，驗(yàn)證是否滿足條件① 和 ③(滿足這兩個(gè)條件 其他的條件一定滿足) 滿足則返回。

#include <iostream>
using namespace std;

//檢查笆焰，已有數(shù)字加起來的和是否超過n
bool checkSum(int * b, int n)
{
    int sum = 0;
    for (int j = 0; j < n; j++)
    {
        sum += b[j];
    }
    return (sum == n) ;
}
//檢查組成是否滿足 “下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)劫谅。”
bool checkcomponet(int * a, int * b, int n)
{
    for (int i = 0; i < n; i++)
    {
        int num = 0;
        for (int j = 0; j < n;j++)
        {
            if (b[j] == a[i])
            {
                num++;
            }
        }
        if (num != b[i])
        {
            return false;
        }
    }
    return true;
}

/*
暴力計(jì)算
in:輸入
out：輸出數(shù)組
n:一共有多少個(gè)數(shù)字
num:當(dāng)前要確定第幾個(gè)數(shù)字
*/
bool findnum(int * in, int * out, int n, int num) 
{
    bool isFind = false;
    for (int i = 0; i < n; i++)
    {
        out[num - 1] = i; //設(shè)當(dāng)前數(shù)為i
        
        //根據(jù)和 與 積 不能大于n 去掉大部分錯(cuò)誤的嘗試 
        int product = 0;
        int sum = 0;
        for (int j = num - 1; j < n; j++)
        {
            product += out[j]*in[j];
            sum += out[j];
        }
        if (sum > n || product > n)
        {
            break;
        }


        if (num == 1)
        {
            if (checkcomponet(in, out, n) && checkSum(out, n))
            {
                isFind = true;
            }
        }
        else
        {
            isFind = findnum(in, out, n, num - 1); 
        }

        if (isFind == true)
        {
            break;
        }
        
    }
    return isFind;
}

int main()
{
    int a[11] = {0,-1,1,2,-2,3,4,5,7,8,10};
    int b[11] = {0};
    bool isfind = findnum(a,b,11,11);

    cout << "a: ";
    for (int i = 0; i < 11; i++)
    {
        cout << a[i]<< ' ';
    }
    cout<<endl;
    if (isfind == true)
    {
        cout << "b: ";
        for (int i = 0; i < 11; i++)
        {
            cout << b[i]<< ' ';
        }
        cout<<endl;
    }
    else
    {
        cout << "no answer can be find!" << endl;
    }
    return 0;
}

這種方式思路比較好理解嚷掠，但是執(zhí)行時(shí)間復(fù)雜度很高捏检，當(dāng)n很大的時(shí)候不可取。但是在網(wǎng)上沒有找到比較好的解法了不皆。
網(wǎng)上找到一個(gè)規(guī)律：如果是n個(gè)連續(xù)的從0到n-1個(gè)數(shù)字贯城，那么，1和2下面的數(shù)是2和1霹娄，0下面的數(shù)是n-3冤狡，其中n是最后一個(gè)數(shù)的下標(biāo)，n-3下面是1