白駿1744号-束手

2822 ワード
アルゴリズム#アルゴリズム# 白駿 ps グリディ テキストリンク
問題を解く
まず入力を正負ベクトルにそれぞれ格納し,0入力の個数を変数にそれぞれ格納する.
次に、負数を降順、正数を昇順に並べ替えます.
並べ替えができているので、量は大数から2つずつ乗せればいいのですが、1と2の場合は加算値がもっと大きいので、加算値と乗算値を比較して、ansにもっと大きな値を加算します.
以降の正数が奇数であれば、残り1つはansに加算されます.
現在、負数に2つの最小を乗じると最大の正数になるので、小数から2つを乗じてpop演算を行い、それを取り除きます.
2つを1つずつ組み合わせて最大の数を生成し、入力数列に0があり、negが空でない場合、この数は0に等しく、(0 n)で0を生成することができるので、popはあなたにあげます.
ex) {-1, -2, -3, 0} -> (-2 -3) + (-1 * 0) = 6
入力数列にゼロがなければ、残りをansに加えるだけです.
ex) {-1, -2, -3} -> (-3 * -2) + (-1) = 5
質問リンク
boj/1744
ソースコード
PS/1744.cpp 
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

vector<int> p;
vector<int> neg;
int zero;
int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		if (a > 0)
			p.push_back(a);
		else if (a == 0)
			zero++;
		else
			neg.push_back(a);
	}
	
	sort(neg.begin(), neg.end(),greater<int>());
	sort(p.begin(), p.end());
	int ans = 0;

	for (int i = p.size() - 1; i >= 1; i -= 2)
	{
		if(p[i] + p[i-1] > p[i] * p[i-1])
			ans += p[i] + p[i - 1];
		else
			ans += p[i] * p[i - 1];
	}
	if (p.size() % 2 == 1)
		ans += p[0];
	for (int i = neg.size() -1; i >=1; i -= 2)
	{
		ans += neg[i] * neg[i-1];
		neg.pop_back();
		neg.pop_back();
	}
	if (!neg.empty() && zero)
		neg.pop_back();
	else if (!neg.empty() && !zero)
		ans += neg[0];
	cout << ans;
}
Router DOM V 4−以前の書き方をまとめておく
親身長と同じ高さdivをつくる方法