大神的世界

想法:

先放右括弧，再放左括弧

以n = 4 為例

A ) B ) C ) D )

目前有ABCD四個位置可以放置

且 A <= 4， B <= 3， C <= 2， D <= 1

若我們用數字表示放置量

那麼依序為

4 0 0 0
3 1 0 0
3 0 1 0
3 0 0 1
2 2 0 0
2 1 1 0
2 1 0 1
2 0 2 0
2 0 1 1
1 3 0 0
1 2 1 0 
1 2 0 1
1 1 2 0 
1 1 1 1 

相關寫法請參照程式碼

這裡要提醒各位

此題用printf, scanf會過

加下列兩行

ios::sync_with_stdio(false);

cin.tie(0)

用cin cout  + endl會TLE

用cin cout + "\n"會更快

不過，就我測出來的時間，反而是上述方法比較快

我以 n = 10 作為測試

printf scanf

1.把printf 那一串寫外面(函式)

43s

2.把printf 那一串寫裡面(同程式碼)

35s

cin cout + endl 加 上面2行

1.把cout 那一串寫外面(函式)

8s

2.把cout 那一串寫裡面

7s

cin cout + "\n" 加 上面2行

1.把cout 那一串寫外面(函式)

~1s

2.把cout 那一串寫裡面

~1s

最後，35s會過7s不會過 == 

這是什麼概念???

程式碼:

#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    int n;
    int bracketsSeq[14];
    int recycle;
    int lastLB;

    while(~scanf("%d", &n))
    {
        memset(bracketsSeq, 0, sizeof(bracketsSeq));
        bracketsSeq[0] = n;

        while(true)
        {
            for(int i = 0; i<n; i++)
            {
                for(int j = 0; j<bracketsSeq[i]; j++)
                    printf("(");
                printf(")");
            }
            printf("\n");

            //找尋最後一個左括弧
            for(lastLB = n-1; bracketsSeq[lastLB] == 0; lastLB--);

            //最後面不能再分了
            if(lastLB == n-1)
            {
                if(lastLB >= 0)
                {
                    //找到最後一個0，並回收後面的左括弧
                    recycle = 0;
                    for(;lastLB>=0 && bracketsSeq[lastLB] != 0; recycle += bracketsSeq[lastLB], bracketsSeq[lastLB] = 0, lastLB--);

                    //全是1
                    if(lastLB < 0)
                        break;

                    //找尋分配者
                    for(lastLB = lastLB-1; lastLB>=0 && bracketsSeq[lastLB] == 0; lastLB--);
                }

                //分配1個左括弧給後面
                bracketsSeq[lastLB]--;
                bracketsSeq[lastLB + 1] = recycle + 1;
            }
            //後面還有可以分的位置
            else
            {
                //分配1個左括弧給後面
                bracketsSeq[lastLB]--;
                bracketsSeq[lastLB + 1] = 1;
            }
        }
    }
}