[BOJ] 2437. 秤.

秤.
アルゴリズム区分:グリディ
質問する
両腕秤で重さを測らなければならない.この秤の両腕の末端には物やピボットを置く皿があり、両腕の長さは等しい.また、秤の片方は秤錘しか入れられず、もう片方は秤量するものしか入れられません.

N個の重量が正の整数の秤錘がある場合は、測定できない整数重量の最大値を計算するプログラムを作成してください.
例えば、重量がそれぞれ3、1、6、2、7、30、1人7個の秤錘の場合、これらの秤錘では計測できない量の浄水重量のうち、最大値は21である.
入力
第1行は秤錘の個数を表す正の整数Nを与える.Nは1以上1000以下である.2行目には秤の重さを表す正の整数がN個あり、真ん中にスペースが隔てられている.1本あたりの秋の重さは1以上1000000以下です.
しゅつりょく
最初の行で指定された測定できない整数重量の最大値を出力します.
入力例1
7
3 1 6 2 7 30 1
サンプル出力1
21
問題を解く
入力した値が整列していない場合は、整列します.
最初の解法では,すべての場合の数を組み合わせて求め,空の値を探す形で実現しようとしたが,Nの最大範囲が1000であるため,すべての場合の数が計算を求める場合に無条件にタイムアウトするため,この方法は利用できないと考えられる.
第二に、空の値を探すために、1から1つずつ増やして、値を作成できるかどうかを決定するプロセスを試みますが、確認を繰り返して各値を作成できる関数を使用すると、タイムアウトが発生します.
質問板の助けで質問に再接触し、
現在選択されている数字が現在選択されている数字よりも小さい場合、この数字は現在選択されている数字(result)から選択された数字(result+v[i])に1つの数字(大きい場合、これまで選択されていた数字+1では創造できなかった最小数)を加えることができます.
これを展開すると、デフォルトではresult>=v[i]-1となり、result以下のすべての数値が作成できる場合は、result+v[i]を作成する場合に置きます.では、v[i]+0、v[i]+1、・・、v[i]+resultまでの数を作成できます.すなわち、resultからresult+v[i]までのすべての数値を作成することができる.
ソースコード

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v;
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	while(n--) {
		int input;
		cin >> input;
		v.push_back(input);
	}
	
	solve();
	
	return 0;
}

void solve() {
	sort(v.begin(), v.end(), less<int>());
	
	int result = 1;
	for(int i = 0; i < v.size(); i++) {
		if(result < v[i]) {
			break;
		}
		
		result += v[i];
	}
	
	cout << result << endl;
}

題出所:https://www.acmicpc.net/problem/24372

カイドウ草が白駿で「そうだ!!」判定を受けた