支配值数目

支配值数目

时间: 1ms        内存:64M

描述:

已知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

提示:

参考答案(内存最优[748]):

#include<stdio.h>
main()
{
	int f[1000],g[1000],m,n,i,j,s = 0;
	scanf("%d %d\n",&m,&n);
	for(i=0;i<m;i++)
	{
		scanf("%d",&f[i]);
	}
	for(i=0;i<n;i++)
	{
		scanf("%d",&g[i]);
	}
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			if(f[i]>g[j])
			{
			s++;
			}
		}
	}
	printf("%d\n",s);
	return 0;
}

参考答案(时间最优[0]):

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int n,m;
    cin>>m>>n;
    int i,j;
    int sum=0;
    int a[1002],b[1002];
    for(i=1; i<=m; i++)
        cin>>a[i];
    for(j=1; j<=n; j++)
        cin>>b[j];
    j=1;
    for(i=1; i<=m; i++)
    {
        while(b[j]<a[i])
        {
            if(j<=n)
                j++;
            if(j==n+1)break;
        }
        sum+=j-1;
    }
    cout<<sum<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注