正经题解｜考前临时抱佛脚

【算法分析】

枚举每道题交给哪边的脑子解决，找到两边时间较大值的最小值。

【参考代码】

#include <iostream>
using namespace std;

const int INF = 2e9;
int l, r, minn, ans; //左脑解题花费时间、右脑解题花费的时间，单科最小花费时间，四科花费的总时间 
int s[5];    //s[i]表示第i个科目的题目数量 
int a[30][5];  //a[j][i] 表示第i个科目的第j个题目解出花费的时间 

//搜索所有可能方案，并维护一个最短时间 
void dfs(int x, int y) {
	if (x > s[y]) {  //终止条件 
		minn = min(minn, max(l, r));
		return;
	}
	l += a[x][y]; //左脑解第x题 
	dfs(x + 1, y);
	l -= a[x][y]; //搜索回溯
	r += a[x][y]; //右脑解第x题 
	dfs(x + 1, y);
	r -= a[x][y];//搜索回溯
}
int main() {
	cin >> s[1] >> s[2] >> s[3] >> s[4];
	for (int i = 1; i <= 4; i++) {
		l = r = 0;   //初始化为 0 
		minn = INF;
		for (int j = 1; j <= s[i]; j++)
			cin >> a[j][i];
		dfs(1, i);  //i科目的第一道题开始搜索 
		ans += minn;
	}
	cout << ans;
	return 0;
}

【时间复杂度】

$O(2^n)$ $n$ 为题目数量

【预计得分】

$100pts$