贪心+dp

首先先用一个贪心的想法把所有的牛排个序

排序方式就是把走路最慢的牛排到最前面

证明：首先显然所有的牛喝水的时间总和是一定的，然后对于每一个牛就是要让最慢的牛提前走

然后我们排好了顺序，接下来考虑如何将每一个人放在哪一号水龙头那里

这就没有什么贪心性质了，那我们考虑dp

首先我们设 $dp_{i,j,k}$ 表示前 $i$ 个人，第一个水龙头总用时为 $j$ ，第二个为 $k$

但是这样我们发现空间复杂度是 $O(N*(N*A_i)^2)$ 无法接受

那我们可以约掉一维

我们记录一个前缀和 $sum_i$ 则 $k=sum_i-j$

那么进行转移：

$$ dp_{i,j}=\min_{1 \leq i \leq n,0\leq j \leq sum_i} \left\{\begin{matrix}\max\left \{ dp_{i-1,j-A_i},j+B_i \right \} (j \ge A_i) \\\max\left \{ dp_{i-1,j},sum_i-j+B_i \right \} \end{matrix}\right. $$

预处理：$dp_{0,0}=0$ ，答案为 $\min_{0\leq i \leq sum_n} \left \{ dp_{n,i} \right \} $

这不只是贪心，还有dp！！！

别问我怎么知道的

读题

1 ≤ N, Ai, Bi ≤ 200。显然不是贪心，不然数据范围不可能这么（良心）小

贪心部分思路

喝水时间的总和是固定的，所以我们让最后回牛栏的时间尽可能少。以b从大到小排序即可。

bool cmp (node a, node b) {
	return a.b>b.b;
}

dp部分思路

很容易想到设：f[i][j][k]为前i头牛，第一个水管喝水时间为j，第二个水管k喝水时间为k时，最晚回到牛栏的时间。

转移：

f[i][j] = max(f[i-1][j-x[i].a][k], j+x[i].b)); //i牛在第一个水管喝水
f[i][j] = max(f[i-1][j][k-x[i].a], k+x[i].b)); //i牛在第二个水管喝水 

这样会爆空间，考虑怎么优化。因为i头牛喝水时间固定，所以j+k等于前i头牛喝水时间总和，这样我们可以把k这一维去掉。那要用到k的时候怎么办？前i头牛喝水时间和-j即可（q[i]-j），别忘记预处理前缀和QwQ

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 210;
	struct node {
		ll a;
		ll b;
	}x[N];
	ll n, ans=0x7f7f7f7f;
	ll q[N], f[N][N*N]; //前i个牛，第一个水管时间j
	bool cmp (node a, node b) {
		return a.b>b.b;
	}
	void work()
	{
		cin>>n;
		for (ll i=1; i<=n; i++)
			cin>>x[i].a>>x[i].b;
		sort(x+1, x+1+n, cmp); //以b从大到小排序 
		for (ll i=1; i<=n; i++)
			q[i] = q[i-1]+x[i].a; //预处理前缀和 
		memset(f, 0x3f, sizeof(f));
		f[0][0] = 0; //不要忘记初始化，前0头牛在水管1喝水时间为0，最晚回栏时间为0 
		for (ll i=1; i<=n; i++) {
			for (ll j=0; j<=q[i]; j++) { //第一个水管用时最多是q[i]，即前i头牛全在水管1喝 
				if (j>=x[i].a) f[i][j] = min(f[i][j], max(f[i-1][j-x[i].a], j+x[i].b)); //在第一个水管
				if (q[i]-j>=x[i].a) f[i][j] = min(f[i][j], max(f[i-1][j], q[i]-j+x[i].b)); //在第二个水管 
			}
		}
		for (ll i=0; i<=q[n]; i++) //求ans 
			ans = min(ans, f[n][i]); //前n头牛，在水管1喝水时间为i，最晚回到牛栏的时间 
		cout<<ans<<'\n';
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

题意：

有n头奶牛，每头牛有喝水时间a和走回时间b，有2个水龙头，所以要把这些奶牛排成两队，问怎么排可以使得最后走回的奶牛返回时间最早

做法：

贪心+dp

可以想到走回慢的要先排

然后具体如何排可以通过dp求解

我们定义f[i][j][k]指前i头牛第k个水龙头排了j的时间的最优返回时间

k这一维是可以省略的，因为可以通过前i头牛a的前缀和加工出来

$f[i][j] = min_{j<=s[i]}(max(f[i-1][j],s[i]-j+b[i]),max(f[i-1][j-a[i]],j+b[i]))$

code:

#include <bits/stdc++.h>
using namespace std;

const long long N = 201;

long long n, mx;

struct node{
	long long a, b;
}arr[N];

long long f[N][N*N], s[N];

void read(){
	cin >> n;
	for(long long i = 1;i <= n; i++){
		cin >> arr[i].a >> arr[i].b;
	}
	sort(arr+1,arr+1+n,[](node x,node y){return x.b > y.b;});
	for(long long i = 1;i <= n; i++){
		s[i] = s[i-1] + arr[i].a;
	}
	return ;
}

void compute(){
	memset(f,127,sizeof(f));
	f[0][0] = 0; 
	for(long long i = 1;i <= n; i++){
		for(long long j = 0;j <= s[i]; j++){
			f[i][j] = INT_MAX;
			if(j >= arr[i].a) f[i][j] = min(f[i][j],max(f[i-1][j-arr[i].a],j+arr[i].b));
			f[i][j] = min(f[i][j],max(f[i-1][j],s[i]-j+arr[i].b));
		}
	}
	long long ans = INT_MAX;
	for(long long i = 0;i <= s[n]; i++){
		ans = min(ans,f[n][i]);
	}
	cout << ans;
	return ;
}

int main(){
	read();
	compute();
	return 0;
}