题解：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)

。

代码如下：

CPP

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

的时间，即为答案。

代码（马蜂优良）：

CPP

#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);
}

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

题解：P6243 [USACO06OPEN] The Milk Queue G

文章操作

解析：

代码（马蜂优良）：

相关推荐

评论

题解：P6243 [USACO06OPEN] The Milk Queue G