题解 P6243 【[USACO06OPEN]The Milk Queue G】
lmrttx
2020-12-02 21:42:11
**贪心+排序**的题目。
第一眼想到排队打水的问题，~~不止我一个吧，~~ 下面我们分析下题目。
如何决定排序顺序呢？
我们有两头牛，分别为 $x$ 与 $y$。
如果 $x$ 排在 $y$ 的前面，那么两头牛的时间之和就是
$$x.1+y.2+max(x.2,y.1)$$
因为,$x.1$ 与 $y.2$ 是**必须耗时间去单独进行的**，而 $x.2$ 与 $y.1$ 是**同时进行**的。
同理，如果 $y$ 在 $x$ 前面，我们可知：
$$y.1+x.2+max(y.2,x.1)$$
就是时间之和。
根据这个关系排序：
```cpp
struct node{
ll a,b;
}cow[30000];
bool cmp(node x,node y){
return min(x.a,y.b)<min(x.b,y.a);
}
```
------------
第一部分结束，到这里时，已经接近AC了。
从前往后循环，记录当前最大值，运用到前缀和。当然，另一种写法可以不用到前缀和，由于题解区已经有这种统计方法了，所以此处不贴。
更详细的注释见代码。
```cpp
for(register ll i=1;i<=n;i++){
sum[i]+=sum[i-1]+cow[i].a;
answer=max(sum[i],answer)+cow[i].b;
//answer为最终答案，由于cow[i].b的时间是必须耗的，所以直接加上。
//sum就是前缀和数组了。它可以统一前面的最优解，最后用sum更新answer就可以了。
//sum的计算和answer的更新就是我们前面介绍的贪心思想。即：cow[i].a与cow[i-1].b是同时进行的。
}
```
------------
好！AC代码贴上！~~我动了些手脚，您直接复制无法AC。拒绝抄袭，共建和谐洛谷！~~
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,answer,sum[30000];
struct node{
ll a,b;
}cow[30000];
bool cmp(node x,node y){
return min(x.a,y.b)<min(x.b,y.a);
}
int main(){
scanf("%lld",&n);
for(register ll i=1;i<=n;i++){
scanf("%lld%lld",cow[i].a,cow[i].b);
}
sort(cow+1,cow+n+1,cmp);
for(register ll i=1;i<=n;i++){
sum[i]+=sum[i-1]+cow[i].a;
answer=max(sum[i],answer)+cow[i].b;
}
printf("%lld",answer);
return 0;
}
```
谢谢阅读，如有不足请指出qwq。