支配值数目

   已知f[]与g[]两个整数数组,元素都是已经从小到大排列,试编写程序,算出f[]中每个元素比g[]中元素大的个数的总数. 换句话说,f[0]比g[]中多少个元素大,f[1]中比g[]中多少个元素大等,这些值的总和就是所要求的答案.

-------------------------------------------------------------------------------------

程序1:

 

#include <stdio.h>

// [8/15/2008 Admin]
int main(void)
{
    int f[] = { 1, 2, 4, 7, 9, 12, 13, 15, 16, 20};
    int g[] = { 4, 5, 7, 8, 9, 10, 11, 13, 16, 19};
    int pf = 0,pg = 0;                //指向f,g的"指针"

    int nf = sizeof(f)/sizeof(int);    //数组长度

    int ng = sizeof(g)/sizeof(int);
    int big_num = 0;

    for(pf=0; pf<nf; pf++)            //遍历一次数组f
    {
        if(f[pf]>=g[pg])big_num += pg;
        while(f[pf]>g[pg] && pg<ng)    
        {
            big_num += 1;
            pg++;
        }
    }
    printf("There are %d Dominance Pairs.\n",big_num);

    return 0;
}

 

程序2:

#include <stdio.h>

int dominance_count(int f[], int g[], int m, int n)
{
    int index_f, index_g;
    int count;
    
    count = index_f = index_g = 0;
    while (index_f < m && index_g < n)
        if (f[index_f] <= g[index_g])
            index_f++;
        else
            index_g++, count += m - index_f;
        return count;
}

void main(void)
{
    int x[] = { 1, 2, 4, 7, 9, 12, 13, 15, 16, 20};
    int nx = sizeof(x)/sizeof(int);
    
    int y[] = { 4, 5, 7, 8, 9, 10, 11, 13, 16, 19};
    int ny = sizeof(y)/sizeof(int);
    
    int dominance_count(int [], int [], int, int), i;
    
    printf("\nDominance Count of two Increasing Arrays\n");
    printf("\n # Array 1 Array 2");
    printf("\n -- ------- -------");
    
    for (i = 0; i < nx; i++)
        printf("\n%3d%10d%10d", i, x[i], y[i]);
    printf("\n\nThere are %d Dominance Pairs.",
        dominance_count(x, y, nx, ny));
}