关于如何排序使得最终的答案最优的总结
例题
- Luogu P1012
- CF2024C
分析
就以先 CF2024C 来展开，题意是给定 \(N\) 个二元组，确定一个可行的排列使得最后的序列逆序对个数最少，注意二元组内部不可以交换顺序
Solution1
详情见 “CF980 Review” 中对这道题的解法，这里不多赘述了。
只是观察这种解法这道题有什么性质：
首先，我们定义的 \(A\) 比 \(B\) 更优，\(A\) 应该放在前面，是指 \(A\) 中的较大元素比 \(B\) 中的较大元素更小，或者说两者的较大值相等，但是前者的较小值更小。
按照我们的方法来交换相邻元素一定不会让答案变得更劣。
不难观察到 如果 \(A\) 比 \(B\) 优，且 \(B\) 比 \(C\) 优，那么一定能够得出 \(A\) 比 \(C\) 优。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int T,n,m;
const int N=2e5;
pair<int,int> a[N];
inline bool cmp(pair<int,int> x,pair<int,int> y)
{
int mx1,mn1,mx2,mn2;
mx1=max(x.first,x.second),mx2=max(y.first,y.second);
mn1=min(x.first,x.second),mn2=min(y.first,y.second);
return (mx1==mx2?mn1<mn2:mx1<mx2);
}
int main()
{
re(T);
while(T--)
{
re(n);
for(register int i=1;i<=n;++i)
{
re(a[i].first),re(a[i].second);
}
sort(a+1,a+n+1,cmp);
for(register int i=1;i<=n;++i)
wr(a[i].first),putchar(' '),wr(a[i].second),putchar(' ');
putchar('\n');
}
return 0;
}
Solution2
官方题解给出了一种更加简洁而且非常容易猜到的排序方式，虽然思维上面还是小有难度，但事实上看来赛时很多人都通过了这道题，这也印证了 oi 比赛不需要严格的证明，如果你猜的结论是正确的，那么就大胆地去应用，错了反正还可以再来，只是要罚时而已 (仅限非oi赛制)
我们只需要按照 \(A\) 这个二元组中两个元素的和把这个二元组序列升序排列就好。
证明可以通过分类讨论的方式来实现，
如果说 \(A\) 的和大于 $B $ 的和，那么要么 \(A\) 的两个值被夹在 \(B\) 的中间，要么 \(A\) 两个值 都比 \(B\) 的大。
在这两种情况下，我们交换 \(A\) 和 \(B\) 一定至少不会使得答案变得更差。
而且，二元组内部的和的大小，如果 \(A\) 比 \(B\) 优，\(B\) 比 \(C\) 优，就一定有 \(A\) 比 \(C\) 优。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
int T,n,m;
const int N=2e5;
pair<int,int> a[N];
inline bool cmp(pair<int,int> x,pair<int,int> y)
{
return x.first+x.second<y.first+y.second;
}
int main()
{
re(T);
while(T--)
{
re(n);
for(register int i=1;i<=n;++i)
{
re(a[i].first),re(a[i].second);
}
sort(a+1,a+n+1,cmp);
for(register int i=1;i<=n;++i)
wr(a[i].first),putchar(' '),wr(a[i].second),putchar(' ');
putchar('\n');
}
return 0;
}
Hack1
那么你会问 ，我为什么不能对于相邻的两个元素，直接比较他们交换位置前后的逆序对数量来定义他们的 优劣 呢？
而且好像似乎也满足 如果 \(A\) 比 \(B\) 优，\(B\) 比 \(C\) 优，就一定有 \(A\) 比 \(C\) 优 的性质。
那我们再仔细思考一下，以上两种解法，我们实际上并没有考虑 \(A=B\) 的情况，因为我们认定他们无论是否交换，对答案是不会存在影响的。
在解法 1 中，\(A=B\) 则意味着两个二元组完全相等，所以显然没有影响。
在解法 2 中，\(A=B\) 则意味着两个二元组要么是相同，要么是完全包含，可以证明如果有 \(B>C\) 或者 \(B=C\) ，就一定有 \(A\ge C\)。
但是在这种解法中，如果 \(A=B,B=C\) ，就不一定有 \(A=C\) 成立，一组hack数据如下。
4 7 ,2 9,7 3
Data generator
#include<bits/stdc++.h>
using namespace std;
int check(int x,int y,int i,int j)
{
return (x>i)+(x>j)+(y>i)+(y>j);
}
int main()
{
int T=300;
while(T--)
{
int x=rand()%10+1,y=rand()%10+1,i=rand()%10+1,j=rand()%10+1,n=rand()%10+1,m=rand()%10+1;
int ans1=check(x,y,i,j),ans2=check(i,j,x,y);
if(ans1>ans2)swap(x,i),swap(y,j);
ans1=check(i,j,n,m),ans2=check(n,m,i,j);
if(ans1>ans2)continue;
if(!(check(x,y,n,m)<=check(n,m,x,y)))
printf("%d %d %d %d %d %d\n",x,y,i,j,n,m);
}
return 0;
}
总结
解决这类问题的三个要素：
- 我们定义的交换相邻元素的方法不会使得答案变得更劣
- 我们定义的优劣比较具有传递性，更形式化地说，如果 $A\ge B,B\ge C $ ，那么必须有 \(A\ge C\) 。
- 务必要考虑等号的情况。
（注：上文的 “\(>\)” 代表 "前者比后者优"）
标签：总结,rand,二元,10,int,pair,最优,排序,check From： https://www.cnblogs.com/Hanggoash/p/18490464