Backjoon Greedy 1744カウント

これはかなり簡単な問題だと直感的に思っていたが、3回間違えた.
負の値は小さい値からソートされます(セクション値が大きいため)
数量は大きい値から並べ替えられます.
そして、正数=n、この高負数の個数=mのとき
nが偶数なら)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-2] x v[n-1]
n奇数の場合)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-3] x v[n-2] + v[n-1]
mが偶数なら)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-2] x v[n-1]
n奇数の場合)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-3] x v[n-2] + v[n-1]
ここで最初のエラーが発生しました.
mが奇数の場合、最小終端値を有するv[n−1]は負数であるため、加算は損失である.
既存の数列に0がある場合は、負の値を追加する必要はありません.
ゼロがあるかどうかをチェックします.
2つ目の間違いは考えても思いつかないので、ネットで調べてみました.
1 1 1 1 1を入力すると
1+1+1+1は(1 x 1)+(1 x 1)より大きい.
1正数列を選ぶときは選ばず、個数だけチェックし、最後にもう一度加算することにします.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(int a, int b) { return a > b; }
bool cmp1(int a, int b) { return a < b; }
int main()
{
	int n;
	int sum = 0;
	int zero_flag = 0; 
	int one_cnt = 0;

	vector<int> seq;
	vector<int> seq_pos;
	vector<int> seq_neg;

	cin >> n;
	while (n--)
	{
		int s;
		cin >> s;
		seq.push_back(s);
	}

	sort(seq.begin(), seq.end(),cmp);
	
	for (int i = 0; i < seq.size(); i++)
	{
		
		if (seq[i] > 1) seq_pos.push_back(seq[i]);
		else if (seq[i] < 0) seq_neg.push_back(seq[i]);
		else if (seq[i] == 0) zero_flag = 1; // 1차오류 
		else if (seq[i] == 1) one_cnt++; // 2차오류 
	}
	sort(seq_neg.begin(), seq_neg.end(), cmp1);
	
	
	if (seq_pos.size() % 2 == 0)
	{
		for (long unsigned int i = 0; i < seq_pos.size(); i = i + 2)
		{
			sum += (seq_pos[i] * seq_pos[i + 1]);
		}
	}
	else
	{
		for (long unsigned int i = 0; i < seq_pos.size()-1; i = i + 2)
		{
			sum += (seq_pos[i] * seq_pos[i + 1]);
		}
		sum += seq_pos[seq_pos.size() - 1];
	}

	if (seq_neg.size() % 2 == 0)
	{
		for (long unsigned int i = 0; i < seq_neg.size(); i = i + 2)
		{
			sum += (seq_neg[i] * seq_neg[i + 1]);
		}
	}
	else
	{
		for (long unsigned int i = 0; i < seq_neg.size() - 1; i = i + 2)
		{
			sum += (seq_neg[i] * seq_neg[i + 1]);
		}
		if (!zero_flag) { // 0이 없다면 
			sum += seq_neg[seq_neg.size() - 1];
		}
		
	}
	
	cout << sum+one_cnt;

	return 0;
}