欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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;
}