【洛谷P2123】皇后游戏

# [题目链接](https://www.luogu.org/problemnew/show/P2123)

这题的

实际上和“流水调度问题”是一样的

（我是不会告诉你我是看了讨论才知道的）

于是我就翻开了我们教练弄来的一本蓝不拉几的叫做“信息学奥赛一本通·提高篇”的书

我们发现，\(A\)机器显然在不停的工作是最优的，要让\(A\)、\(B\)的总时间最短，就是要让\(B\)机器的空闲时间最短

而最终时间的求法恰好是题目中的式子（在上一件产品在\(B\)机器加工完，并且当前产品在\(A\)机器上加工完的时候，把当前产品放到\(B\)机器上加工）

怎样让\(B\)的空闲时间最小呢？显然，先生产\(a<b\)的产品，再生产\(a>b\)的产品是可以减少“\(A\)机器工作时，\(B\)机器没有活干”的情况

我们可以意会一下，我们要尽量地让\(B\)机器跟不上\(A\)机器的速度，好减少\(B\)机器的空闲时间，而且要避免\(A\)机器生产一个加工时间很长的产品时，\(B\)机器没有“存货”了

所以我们先生产\(a\)小\(b\)大的零件，多搞一些“存货”，减少B机器的空闲时间

排个序就行了

然而这和我不会证明有什么关系

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define int long long

const int N=20010;

int T,n,cnt1,cnt2,c[N];

struct NODE{

	int x,y;

} t[N],s1[N],s2[N];

inline bool cmp1(NODE a,NODE b){

	return a.x<b.x;

}

inline bool cmp2(NODE a,NODE b){

	return a.y>b.y;

}

#undef int

int main()

#define int long long

{

	scanf("%d",&T);

	while(T--){

		scanf("%lld",&n);

		cnt1=cnt2=0;

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

			scanf("%lld%lld",&t[i].x,&t[i].y);

			if(t[i].x<=t[i].y) s1[++cnt1]=t[i];

			else s2[++cnt2]=t[i];

		}

		sort(s1+1,s1+1+cnt1,cmp1);

		sort(s2+1,s2+1+cnt2,cmp2);

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

			t[i]=s1[i];

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

			t[cnt1+i]=s2[i];

		c[1]=t[1].x+t[1].y;

		int sum=t[1].x;

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

			sum+=t[i].x;

			c[i]=max(c[i-1],sum)+t[i].y;

		}

		printf("%lld\n",c[n]);

	}

	return 0;

}