题解 P2123 【皇后游戏】

我一开始做这道题也是按照min(ai,bj)<=min(aj,bi)公式排序，而在看题解后我却发现了这个做法竟然不对（QAQ），而楼下的****dalao****的排序方式我看完之后一直不理解为什么这样排序还满足min(ai,bj)<=min(aj,bi)（可能是因为我太菜了），经过我漫长的思索后，终于理解了那样排序的精妙之处 我写这篇题解是给像我这样的蒟蒻一个更容易的理解 建议把我的题解和之前那几位****dalao****的题解结合看，毕竟我没给公式证明 （如果您太强，可以直接忽略掉我这篇题解QAQ） ## 思路 通过相邻交换法可得到 min(ai,bj)<=min(aj,bi) 这个简单而又精妙的公式，既然前面的****dalao****给出了证明，我这里就直接忽略了（逃 我就直接从楼下****dalao****的排序出发了  ``` struct node { int x,y,d; bool operator <(node a) const { if (d!=a.d) return d<a.d; if (d<=0) return x<a.x; return y>a.y; } }a[20005]; ``` 把min(ai,bj)<=min(aj,bi)记为①式; d表示的是a[i].x与a[i].y的大小，若x>y，则把d赋成1，x==y时d=0，x<y时d=-1 因为排序的第一步是比较d的值，我来解释一下（其实我一开始没看懂QAQ） 可以举个例子：若d不相等，设ai<bi,aj>bj，此时d<a.d 若ai<bj,则ai一定是这四个值中的最小值，所以min(ai,bj)就等于ai,又因为ai为最小值，所以①式成立 若ai>bj,则bj一定是这四个值中的最小值，所以min(ai,bj)就等于bj,又因为bj为最小值，所以①式成立 所以这个排序看似没有按①式排序，实则却巧妙穿插,所以楼下****dalao****太强了%%% 以下是我的代码 ``` #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; struct node { int l; int r; int xuanxue; //由于一开始没看懂dalao的代码，所以命名为xuanxueQAQ }a[20010]; int n,t; long long c[20010],f[20010]; int cmp(node a,node b) { if(a.xuanxue!=b.xuanxue) return a.xuanxue<b.xuanxue; if(a.xuanxue<=0&&b.xuanxue<=0) return a.l<b.l; return a.r>b.r; } int main() { scanf("%d",&t); for(int i=1;i<=t;i++) { // memset(c,0,sizeof c); // memset(f,0,sizeof f); int n; scanf("%d",&n); for(int j=1;j<=n;j++) { scanf("%d%d",&a[j].l,&a[j].r); if(a[j].l-a[j].r<0) a[j].xuanxue=-1; else if(a[j].l-a[j].r>0) a[j].xuanxue=1; else a[j].xuanxue=0; } sort(a+1,a+n+1,cmp); c[1]=a[1].l+a[1].r; f[1]=a[1].l; for(int j=2;j<=n;j++) { f[j]=a[j].l+f[j-1]; c[j]=max(c[j-1],f[j])+a[j].r; } printf("%lld\n",c[n]); } return 0; } ```