【qduoj】【数组合并】
程序员文章站
2024-03-17 17:10:16
...
题目:
Description
现在呢有两个整形数组,a[n]和b[m],而且已经知道这两个数组都是非降序数组。现在呢就有一个工作需要你来完成啦。对于a中的每个元素a[i]在b中寻找<=a[i] 的元素个数,个数记为x[i]。但是我们并不关心每个x[i],现在只要你计算所有x[i]的和就可以啦。
Input
输入包含单组样例第一行两个整数 n,m
第二行n个整数代表a数组元素。第三行m个整数代表b数组元素。保证a,b数组元素非递减排列。数组元素为int类型1=<m,n<=10000000;
Output
输出包含一行仅一个整数,表示结果。注意结果比较大,注意用long,long
Sample Input 1
3 4 1 2 5 3 5 5 48
Sample Output 1
3
题意不解释了;
解题思路:被自己蠢哭了,看着时限是3S ,居然试图双重暴力走两次1e7的循环,光荣T ,因为自己出去玩耍,缺了一节课,对于归并排序的理解没有达到应有的程度,别人哒哒哒几分钟A 了,自己入坑一个小时。。。
其实最后讲解后,没啥困难的地方,就是在j走的时候不回头就好,这样就是i j都走了一次,时间复杂度很低。
ac代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+5;
int num1[maxn];
int num2[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&num1[i]);
for(int j=1;j<=m;j++)
scanf("%d",&num2[j]);
int j=1;
ll ans=0;
for(int i=1;i<=n;i++)
{
while(num1[i]>=num2[j]&&j<=m) j++;
ans+=j-1;
}
cout<<ans<<endl;
return 0;
}
上一篇: unity3d UI性能优化。
下一篇: 69. x 的平方根