题解 P2123 【皇后游戏】
xmh060606
2019-04-19 15:14:51
看了各位大佬的题解，发现大多数都是用
#### min(a i ,b j )≤min(a j ,b i)
进行排序的
但是在参考了 一本叫做“信息学奥赛一本通·提高篇”的书 以后，发现了有一个东西叫“流水调度问题”，我们发现，A机器显然在不停的工作是最优的，要让A、B的总时间最短，就是要让B机器的空闲时间最短 而最终时间的求法恰好是题目中的式子（在上一件产品在B机器加工完，并且当前产品在A机器上加工完的时候，把当前产品放到B机器上加工）
怎样让B的空闲时间最小呢？显然，先生产a<b的产品，再生产a>b的产品是可以减少“A机器工作时，B机器没有活干”的情况
我们可以意会一下，我们要尽量地让B机器跟不上A机器的速度，好减少B机器的空闲时间，而且要避免A机器生产一个加工时间很长的产品时，B机器没有“存货”了
所以我们先生产a小b大的零件，多搞一些“存货”，减少B机器的空闲时间，排个序就行了。
但是证明这一块还无法给出绝对的证明，不知道有没有大佬能够在评论里说一下......
ac代码如下：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
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
{
cin>>T;
while(T--){
cin>>n;
cnt1=cnt2=0;
for(int i=1;i<=n;++i){
cin>>&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;
}
cout<<c[n]<<endl;
}
return 0;
}
```