lanqiaoOJ 3333：肖恩的排序 ← 双指针+排序（从大到小）

【题目来源】
https://www.lanqiao.cn/problems/3333/learning/

【题目描述】
肖恩提出了一种新的排序方法。
该排序方法需要一个标准数组 B 和一个待排序数组 A。在确保对于所有位置 i 都有 A[i]>B[i] 的前提下，肖恩可以自由选择 A 数组的排序结果。请计算按照这种排序方法，待排序数组 A 可能的结果有多少种。
对于任意一个位置 i，如果两次排序后 A[i] 不是同一个数字，那么这两种排序方式就被称为是不同的。结果可能很大，你需要将结果对 10^9+7 取余。

【输入格式】
第一行输入一个数字 n，为两个数组的长度。
第二行输入 n 个数字，表示待排序数组 A 中的所有元素。
第三行输入 n 个数字，表示标准数组 B 中的所有元素。
数据保证 1≤n≤10^5，1≤A[i]≤10^9，1≤B[i]≤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[0]=5，数组 A 中比 5 大的数为 8，6，故有 2 种选择；
B[1]=4，数组 A 中比 4 大的数为 8，6，5，但上一个位置使用了 1 个，故有 2 种选择；
B[2]=3，数组 A 中比 3 大的数为 8，6，5，但前两个位置使用了 2 个，故有 1 种选择；
B[3]=2，数组 A 中比 2 大的数为 8，6，5，3，但前三个位置使用了 3 个，故有 1 种选择；
B[4]=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[maxn],b[maxn];
int n;

bool down(int u,int v) {
    return u>v;
}

int main() {
    cin>>n;
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<n; i++) cin>>b[i];

    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[i]>b[j]) {
            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/