lanqiaoOJ 3333:肖恩的排序 ← 双指针+排序(从大到小) ...

打印 上一主题 下一主题

主题 822|帖子 822|积分 2466

【题目来源】
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 种。

【算法代码】
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int MOD=1e9+7;
  5. const int maxn=1e5+5;
  6. LL a[maxn],b[maxn];
  7. int n;
  8. bool down(int u,int v) {
  9.     return u>v;
  10. }
  11. int main() {
  12.     cin>>n;
  13.     for(int i=0; i<n; i++) cin>>a[i];
  14.     for(int i=0; i<n; i++) cin>>b[i];
  15.     sort(a,a+n,down);
  16.     sort(b,b+n,down);
  17.     LL cnt=0,ans=1;
  18.     for(int i=0,j=0; j<n; j++) { //double pointer
  19.         while(i<n && a[i]>b[j]) {
  20.             cnt++,i++;
  21.         }
  22.         ans*=cnt; //Multiplication principle
  23.         cnt--; //Used one, Minus it
  24.         ans%=MOD;
  25.     }
  26.     cout<<ans<<endl;
  27.     return 0;
  28. }
  29. /*
  30. in:
  31. 5
  32. 2 3 5 6 8
  33. 1 2 3 4 5
  34. out:
  35. 4
  36. */
复制代码



【参考文献】
https://www.lanqiao.cn/problems/3333/learning/


 

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

铁佛

金牌会员
这个人很懒什么都没写!

标签云

快速回复 返回顶部 返回列表