D - Cooking
[Q] https://atcoder.jp/contests/abc204/tasks/abc204_d
1. 最も効率よくオーブンを使うとは？
A. 総調理時間の半分ずつに分配できれば一番よさそう。
Q.
1 2 3 4
があったとして、
1 + 2 + 3 + 4 = 10 // sum
1+4 , 2+3
でオーブン分けすれば、5分で終わる。2. bool DP[100010] = その時間に割り振ることができるか、で管理。
もしsum/2を超える解答があれば、都度、sum/2に近い値をansの候補としてメモしておく。
3. 初期状態は、DP[0] = true。0秒の調理が可能としておく。
Q. 入力例1
5
8 3 7 2 5
0. 開始用意
bool DP[100010]{} を用意。全部0 ( false ) を入れておく。
DP[0] = true としておく。
1. 総時間を求める
sum = 8 + 3 + 7 + 2 + 5 // 25
sum/2 = 12 なので、12 + 13 に調理時間を分けるのが理想とわかる。
最も 12 に近づける調理時間を探そうと思う。
2. DP。
1) 8
DP[0] -> DP[0+8] = true
DP[0] = true
DP[8] = true の2データがとれる
2) 3
DP[0] -> DP[0+3] = true
DP[8] -> DP[8+3] = true
DP[0] = true
DP[3] = true
DP[8] = true
DP[11] = true の4データがとれる
3) 7
DP[0] -> DP[0+7] = true
DP[3] -> DP[3+7] = true
DP[8] -> DP[8+7] = true
DP[11] -> DP[11+7] = true
DP[0] = true
DP[3] = true
DP[7] = true
DP[8] = true
DP[11] = true
DP[15] = true
DP[18] = true の7データがとれる。
ここで、{ 15, 18 } が 12 を超えたので、
12以上の最小値である ans = 15 をメモしておく。
4) 2
5) 5
これを捜査すると、
DP[12] = true
となるので、一方の調理時間が 12 とわかる。( 今回は理想値がとれる ）
解答は、max( sum - 12 , 12 )なので、
A. 13実装
bool DP[100010];
int main(){
cincout();
ll N;
cin >> N;
ll T[N];
rep(i, N) cin >> T[i];
ll sum = 0;
rep(i, N) sum += T[i];
ll ans = oo;
DP[0] = true;
rep(i, N){
ll t = T[i];
for(ll j=sum/2; j>=0; --j){ // sum/2 -> 0 の上から走査していく。 0からだと重複しちゃう
if (DP[j]){
DP[j+t] = true;
if (j+t >= sum/2){
chmin(ans, j+t);
}
}
}
}
cout << max(ans, sum - ans) << endl;
}