atcoder

# # Problem

## # Input

$N$
$t_1$
$t_2$
...
$t_N$

• $N$ - The number of tasks
• $t_N$ - Time to process task$i$

## # Output

The minimum total time to process all the tasks in 2 parallrl.

# # Explanation

It can be solved with bit exhaustive search as each task has 2 choices.
$N$ is enough small.
On the other hand, it can be solved with greedy algorithm as well.
In general, greedy algorithms are faster if they can be applied.

# # Time complexity

$O(2^N)$

## # Greedy algorithm

For sorting tasks $O(N \log{N})$.
For greedy algorithm $O(N)$.

$O(N \log{N})$

# # Solution

## # Bit exhaustive search

Int N, _t;
vector<Int> T;

void input() {
cin >> N;
while (cin >> _t) T.push_back(_t);
}

Int dfs(Int t, Int time1, Int time2) {
if (t >= N) return max(time1, time2);
return min(
dfs(t + 1, time1 + T[t], time2),
dfs(t + 1, time1, time2 + T[t])
);
}

void solve() {
cout << dfs(0, 0, 0) << endl;
}

int main(void) {
input();
solve();
return 0;
}


## # Greedy algorithm

Int greedy() {
Int a = 0, b = 0;
for (auto t: T) {
if (a < b) a += t;
else b += t;
}
return max(a, b);
}

void solve() {
sort(span_all(T));
reverse(span_all(T));
cout << greedy() << endl;
} Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!