支配值数目
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:130 测试通过:94
描述
已知f[]与g[]两个整数数组，元素都已经从小到大排好序，请写一个程序，算出f[]中比g[]中元素大的对数。换句话说，f[0]比g[]中多少个元素大，f[1]比g[]中多少个元素大等，这些值的总和就是要求的答案。
举个例子，如果f[]中有1，3，5，7，9，而g[]中有2，3，4，7，8。
那么：
f[0]比g[]中的所有元素都小；
f[1]比g[0]大；
f[2]比g[0]、g[1]、g[2]大；
f[3]比g[0]、g[1]、g[2]大；
f[4]比g[0]、g[1]、g[2]、g[3]、g[4]大；
所以答案是0+1+3+3+5=12
输入
第一行为两个整数m, n(1≤m, n≤1000)，分别代表数组f[], g[]的长度。
第二行有m个元素，为数组f[]。
第三行有n个元素，为数组g[]。
输出
输出支配值。
样例输入
5 5
1 3 5 7 9
2 3 4 7 8
样例输出
12
提示
你能想出O(n+m)的算法吗?^_^
题目来源
NUAA
分析：略，水题之一。
#include <stdio.h>
int main()
{
int n,m,*p,*q,i,j,k,s=0;
scanf("%d%d",&n,&m);
p=new int[n];
q=new int[m];
for (i=0;i<n;i++)
{
scanf("%d",&p[i]);
}
for (i=0;i<m;i++)
{
scanf("%d",&q[i]);
}
j=0;
for (i=0;i<n;i++)
{
while(p[i]>q[j])
{
if (j<m)
j++;
else
break;
}
s+=j;
}
printf("%d\n",s);
}