题解：P6243 [USACO06OPEN] The Milk Queue G

· · 题解

解析：

题目还是比较水的，凭紫有点高，绿差不多。

这是一道明显的贪心题。

首先，遇到这种类型的题，我们第一时间会想到排序。

大致目标已制定，怎么排序又成了一个问题，既然他是要求最小的时间，那很明显，第一道工序和第二道工序的时间要尽可能的平均，所以我们可以取一个 \min 。

例如：

当有两头牛 1,2 需要你决定谁先来时，该怎么办？

我们有两种安排，两种安排分别有：

1$ 在 $2$ 的前面： $A_1+B_2+ \max A_2,B_1 2$ 在 $1$ 前面： $A_2+B_1+ \max A_1,B_1

我们想让前者时间比后者少，那么所列的式子就是： \min ⁡(A_1,B_2)<\min (⁡A_2,B_1) 。

代码如下：

int cmp(cow o,cow p){
    return min(o.a,p.b)<min(p.a,o.b);
}

注，这里的 cow 是结构体。 接着就很简单了，我们可以开一个for 循环来统计时间。

统计时间时，扫一遍 A的前缀和。每次取前缀和和当前 A 和 B 时间的最大值，因为如果 A 大于 B ，说明 FJ 太慢，拉低了 Rob 的速度。然后加上 B 的时间，即为答案。

代码（马蜂优良）：

#include<bits/stdc++.h>
using namespace std;
int n,cnt,ans;
struct cow{
    int a,b;
}x[100001];
int cmp(cow o,cow p){
    return min(o.a,p.b)<min(p.a,o.b);
}
int main(){
    scanf("%d",&n);
    for(int i=1,xx,yy;i<=n;i++)
    scanf("%d%d",&xx,&yy),x[i].a=xx,x[i].b=yy;
    sort(x+1,x+n+1,cmp);
    for(int i=1;i<=n;i++)
        cnt+=x[i].a,ans=max(ans,cnt)+x[i].b;
    printf("%d",ans);
}

完结撒花，谢谢，点个赞吧