【题目来源】
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[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/
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |