ブルーブリッジカップ最大積C++アルゴリズムHERODINGのブルーブリッジカップを高める道

リソース制限時間制限:1.0 sメモリ制限:512.0 MB問題説明n個数に対して、そこからm個数を取り出し、このm個数の積を最大にするにはどうすればいいですか?入力フォーマットの1行目の1つの数は、データ群数の1組当たりの入力データの合計2行を示す.1行目は、合計数の個数nと、取るべき数の個数mとを与え、1<=n<=m<=15とする.2行目は、このn個の数を順次与え、各数値の範囲は、a[i]の絶対値が4以下であることを満たす.出力フォーマットは、データのセットごとに1行出力され、最大の積となります.サンプル入力1 5 5 1 2 3 4 2サンプル出力
48
问题の考え方:これは简単に见える问题ですが、その中には秘密が隠されていて、私が初めてやった时、私は入力したnの数をソートして、直接最大のいくつかに乗じて结果を出すことができて、このようにするのは大きな抜け穴があることを発见して、もし2つのマイナスの数が2つの正の数より大きいならば、それではこのようなソートは意味がありませんか?実はそうではありません.巧みな方法でこの問題を解決することができます.ループ時に現在の一番前の2つの数と一番後ろの2つの数の積の値の大きさを比較します.もし現在の大きさが大きいならば、1人1人に乗じて、もし小さいならば、負数の乗の結果が大きいことを説明して、負数は2つ2つに乗じて、コードは以下の通りです.

#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std; 
int a[20]; 
int main() 
{ 
	int t; 
	int n, m; 
	int i, j; 
	int now1, now2; 
	long long sum;//      int     
	cin >> t;
	while(t--) 
	{ 
		cin >> n >> m;
		for(i = 0; i < n; i ++) 
		cin >> a[i]; 
		sort(a, a + n); 
		sum = 1; 
		for(i = n - 1, j = 0; i >= j && m !=0 ; i --) 
		{ 
			now1 = a[i] * a[i - 1]; 
			now2 = a[j] * a[j + 1]; 
			if(now1 <= now2 && m >= 2) 
			{//  now1==now2    now2 
			//                
				sum *= now2; 
				i ++; 
				j += 2;
			    m -= 2;//           。 
			}
			 else 
			 { 
			 	sum *= a[i]; 
			 	m --;//           。 
			 } 
		} 
		cout << sum << endl;
	} 
	return 0; 
}

このお兄さんの分かち合いに感謝します.https://blog.csdn.net/enjoying_science/article/details/44246083