题解 AT945 【高橋君とお肉】

原题

来一篇正经的题解QwQ

显然我们要把肉分成耗费时间尽量平均的两堆。

于是考虑二分答案

那么怎么检测一个答案的正确性呢？

我们可以跑一个背包dp，让第一个烤肉架烤尽可能多的肉，最后检测第二个烤肉架能不能烤完剩下的肉即可。

时间复杂度\(O(nlog^2n)\)。

const int N = 2e2 + 10;
const int inf = 0x3f3f3f3f;
int n,sum;
int a[10];
int dp[N];
bool check(int x)
{
	memset( dp , 0 , sizeof(dp) ); // 别忘了初始化背包 
	for(int i = 1;i <= n;i++)
		for(int j = x;j >= a[i];j--) // 一维背包dp
			dp[j] = max( dp[j] , dp[ j - a[i] ] + a[i] );
	return sum - dp[x] <= x; // 第二个烤肉架能否在x时间内烤完剩下的肉 
}
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i],sum += a[i];
	int l = 0,r = N;
	while(l < r) // 二分答案
	{
		int mid = l + r >> 1;
		if( check(mid) )
			r = mid;
		else
			l = mid + 1;
	}
	cout << l << endl; // AT不换行见祖宗
    return 0;
}