Codeforces 1406B - Maximum Product (暴力搜尋 Brute force)

題目大意：

給你一組數列裡面含有正、負整數，試問從中找出 5 個數字乘起來數字最大

分析：

先排序讀進來的全部數列，之後進行窮舉。

窮舉共有三種方法：

全部 5 個數字選最大的正整數
選 3 個最大正整數 + 2 個最小負整數
選 1 個最大正整數 + 4 個最小負整數

Why? 怎麼是這樣做呢?

由於我們負負得正，我們沒辦法確定說到底選誰比較好，但我們可以用窮舉的方式來找出最好的解法。
只要進行排序，最小的兩個負數相乘肯定會比其他的負數相乘來的更大，以此類推，最大的兩個正整數相乘肯定會比其他的正整數相乘更大。

參考連結

Codeforces Round #670 (Div. 2) 深夜掉分（A - C题补题）

心得

這題其實很簡單的，但是我把它想得太複雜了。這…這就是社會的歷練嗎，明明小學生都可以解開的簡單題目，我花了一小時半都沒有解出來。這題出的好呀，直接打中的思考盲點，好過癮，讓我學起來了！

我原本是想要用遞迴解開但我一直錯呀，真的比賽思考很久都還是沒有解開，好討厭。結果我把她想得太困難了，用簡單的小技巧就能解開了。

遞迴解法是選出 9 個數字，其中 5 個為正整數最大，4 個為負整數最小，然後進行遞迴判斷，之後進行優化，但只能過題目的測資，之後就不行了XD，我的技術還是不夠承受呀XD

感謝 RioTian 大神分享程式碼讓我可以看到這種程式解法，讓我可以了解到這種窮舉解法，讓我學習了一課，謝謝大神讓我能夠往前成長一步。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200010
#define ll long long
using namespace std;
ll t , n , a[MAXN] = {} ;

int main()
{
//#ifdef LOCAL
//    freopen("in1.txt" , "r" , stdin );
//#endif // LOCAL
    cin >> t ;
    while(t--){
        cin >> n ;
        for(int i = 0 ; i < n ; i++)
            cin >> a[i] ;
        sort(a , a + n);

        ll ans[5] = {} ;
        ans[0] = a[n-1] * a[n-2] * a[n-3] * a[n-4] * a[n-5] ;
        ans[1] = a[n-1] * a[n-2] * a[n-3] * a[0] * a[1] ;
        ans[2] = a[n-1] * a[0] * a[1] * a[2] * a[3] ;
        sort(ans,ans+3);
        cout << ans[2] << '\n' ;
    }

    return 0;
}

題外話

這裡是我的遞迴解法，有人要幫我修改這程式幫助我通過嗎？如果通過私訊我告訴我好嗎XD，謝謝你啦

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define ll long long
using namespace std;
struct lln{
    ll num , neg ;
};
deque<lln> dnum;
int t , n ;
ll maxn = 0;
int compare(lln a , lln b){
    return  a.num < b.num ;
}

void p(int index , ll sum , int i , ll intNeg ){
    //cout << index << ' ' << sum << ' ' << i << ' ' << intNeg << '\n' ;

    if(index >= 5){
        maxn = max(sum,maxn) ;
        //cout << sum << '\n' ;
        return ;
    }
    if(i < 0 )
        return ;
    p(index +1 , sum * dnum[i].num * (dnum[i].neg? -1 : 1) , i-1 , intNeg+dnum[i].neg);

    if((intNeg+dnum[i].neg) % 2 == 1){
        p(index, sum , i-1 , intNeg);
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r" , stdin );
#endif // LOCAL

    lln temp ;

    cin >> t ;
    while(t--){
        cin >> n ;
        dnum.clear();
        maxn = -1e15;
        for(int i = 0 ; i < n ; i++){
            cin >> temp.num ;
            if(temp.num < 0){
                temp.neg = 1 ;
                temp.num *= -1 ;
            }
            else
                temp.neg = 0 ;
            //cout << temp.num << ' ' << temp.neg << '\n';
            dnum.push_back(temp) ;
        }
        //cout << '\n' ;
        sort(dnum.begin() , dnum.end(), compare ) ;
        p(0,1,n-1,0);
        cout << maxn << '\n' ;
    }



    return 0;
}