BZOJ1727：[Usaco2006 Open]The Milk Queue挤奶队列

我对\(Jhonson\)算法的理解：https://www.cnblogs.com/AKMer/p/9863620.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1727

\(Jhonson\)算法裸题，题目还告诉你如果某头奶牛先于另一头奶牛开始进行第一道工序，那么她开始第二道工序的时间也一定在那一头奶牛之前，可谓非常良心了。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=25005;

int n,ans;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct cow {

	int a,b;

	bool operator<(const cow &tmp)const {

		return min(a,tmp.b)<min(tmp.a,b);//如果写<=的话莫名ＲＥ，求大佬指教。写成<也不影响正确性

	}

}p[maxn];

int main() {

	n=read();

	for(int i=1;i<=n;i++)

		p[i].a=read(),p[i].b=read();

	sort(p+1,p+n+1);int T=0;

	for(int i=1;i<=n;i++) {

		ans+=p[i].a;

		T=p[i].b+max(T-p[i].a,0);//排完序直接模拟就可以了

	}

	printf("%d\n",ans+T);

	return 0;

}

巴特西

BZOJ1727：[Usaco2006 Open]The Milk Queue挤奶队列

最新文章

热门文章