lanqiaoOJ 3333：肖恩的排序 ← 双指针+排序（从大到小）
【题目来源】https://www.lanqiao.cn/problems/3333/learning/
【题目形貌】
肖恩提出了一种新的排序方法。
该排序方法需要一个尺度数组 B 和一个待排序数组 A。在确保对于所有位置 i 都有 A>B 的条件下，肖恩可以自由选择 A 数组的排序结果。请计算按照这种排序方法，待排序数组 A 可能的结果有多少种。
对于任意一个位置 i，如果两次排序后 A 不是同一个数字，那么这两种排序方式就被称为是差别的。结果可能很大，你需要将结果对 10^9+7 取余。
【输入格式】
第一行输入一个数字 n，为两个数组的长度。
第二行输入 n 个数字，表现待排序数组 A 中的所有元素。
第三行输入 n 个数字，表现尺度数组 B 中的所有元素。
数据保证 1≤n≤10^5，1≤A≤10^9，1≤B≤10^9。
【输特别式】
输出一个数字，表现所有的分列数对 10^9+7 取余后的结果。
【输入样例】
5
2 3 5 6 8
1 2 3 4 5
【输出样例】
4
【说明】
一共有以下四种符合条件的排序后的A数组：
2，3，5，6，8，
2，3，6，5，8，
2，3，8，5，6，
2，3，5，8，6。
【算法分析】
● 对一维数组元素从大到小进行排序的方法：
（1）利用 sort(a,a+n,greater＜int＞())；对数组 a 的 n 个元素从大到小排序：https://blog.csdn.net/hnjzsyjyj/article/details/144239572
（2）自界说比较函数 down 作为 sort 函数的参数实现数组元素从大到小排序：https://blog.csdn.net/hnjzsyjyj/article/details/144329247
本题之所以使用从大到小排序，重要是可以大大降低计算量。
● 样例分析
对数组 A 从大到小排序后是 8 6 5 3 2，对数组 B 从大到小排序后是 5 4 3 2 1。易知：
B=5，数组 A 中比 5 大的数为 8，6，故有 2 种选择；
B=4，数组 A 中比 4 大的数为 8，6，5，但上一个位置使用了 1 个，故有 2 种选择；
B=3，数组 A 中比 3 大的数为 8，6，5，但前两个位置使用了 2 个，故有 1 种选择；
B=2，数组 A 中比 2 大的数为 8，6，5，3，但前三个位置使用了 3 个，故有 1 种选择；
B=1，数组 A 中比 1 大的数为 8，6，5，3，2，但前四个位置使用了 4 个，故有 1 种选择。
依据乘法原理，A 数组符合要求的排序结果有 2×2×1×1×1=4 种。
【算法代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;
const int maxn=1e5+5;
LL a,b;
int n;
bool down(int u,int v) {
return u>v;
}
int main() {
cin>>n;
for(int i=0; i<n; i++) cin>>a;
for(int i=0; i<n; i++) cin>>b;
sort(a,a+n,down);
sort(b,b+n,down);
LL cnt=0,ans=1;
for(int i=0,j=0; j<n; j++) { //double pointer
while(i<n && a>b) {
cnt++,i++;
}
ans*=cnt; //Multiplication principle
cnt--; //Used one, Minus it
ans%=MOD;
}
cout<<ans<<endl;
return 0;
}
/*
in:
5
2 3 5 6 8
1 2 3 4 5
out:
4
*/
【参考文献】
https://www.lanqiao.cn/problems/3333/learning/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]