大神的世界

迴圈

輸入n m

輸入數字

將數字小到大排序

開始搜尋

搜尋

迴圈

判別是否可加

可

相加 (即可用空間減少)

紀錄數字 及 位置

如果可用空間 = 0

輸出

否

將以加部分拿出

並且設定下次開始判別的位置

若下次判別的位置回到0或超出範圍(n)

跳出迴圈

註:

i--  :  因為for迴圈會把i+1所以先減在加

ansPtr < n : 此情況發生在 級數<m 時

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

void search_seq();
void print();

int n, m;
int arr[35];
int ans[35][2];
int ansPtr;

int main()
{
    while(cin >> n >> m)
    {
        for(int i = 0; i<n; i++)
            cin >> arr[i];

        sort(arr, arr+n);

        search_seq();
    }
}

void search_seq()
{
    bool Bprint = false;
    int leave;
    int i;

    memset(ans, 0, sizeof(ans));

    for(ansPtr = i = 0, leave = m; ansPtr < n ; i++)
    {
        if(arr[i] <= leave && i<n)
        {
            leave -= arr[i];
            ans[ansPtr][0] = arr[i];
            ans[ansPtr++][1] = i;

            if(leave == 0)
            {
                print();
                Bprint = true;
            }

        }
        else
        {
            while( (i==n || leave < arr[i]) && ansPtr > 0)
            {
                leave += ans[--ansPtr][0];
                ans[ansPtr][0] = 0;
                i = ans[ansPtr][1] + 1;
            }

            if( (leave < arr[i] && ansPtr == 0) || i==0 || i == n)
                break;

            i--;
        }
    }

    if(Bprint == false)
        cout << "-1\n";
}

void print()
{
    for(int i = 0; i<ansPtr; i++)
        cout << ans[i][0] << " ";
    cout << endl;
}