刚才做的那道题比较简单，再做一道。
问题描述:已知f[]与g[]两个整数数组，元素都已经从小到大排列，请写一个程序，算出f[]比g[]中元素大的对数。换句话说，f[0]比g[]中多少个元素大，f[1]比g[]中多少个元素大，等等，这些值的总和就是要求的答案。举个例子，如果f[]中有1,3,5,7,9,而g[]中有2,3,4,7,8，那么答案就是12。
思路:这个题需要注意的地方就是,两个数组都是从小到大排序的，所以，如果f[1]都大于g[]中所有整数时，那么f[2],f[3]等等都会大于g[]中所有整数。下面是代码:
1 #include <stdio.h> 2 #define MAX 1000 3 4 int f[]={1,3,5,7,9}; 5 int g[]={2,3,4,7,8}; 6 int len_f=sizeof(f)/sizeof(int); 7 int len_g=sizeof(g)/sizeof(int); 8 int sum=0; 9 void count(); 10 11 int main() 12 { 13 int result[MAX]={0}; 14 int i,j; 15 int flag_i; 16 for(i=0,j=0;i<len_f&&j<=len_g;) 17 { 18 if(j==len_g) //如果f[]中，从中间开始就都比g[]大，那么就加起来就可以了 19 { 20 sum+=result[i]; 21 for(j=i+1;j<len_f;j++) 22 { 23 result[j]=result[i]; 24 sum+=result[j]; 25 } 26 break; 27 } 28 if(i!=0 && flag_i==1) 29 { 30 result[i]+=result[i-1]; 31 flag_i=0; 32 } 33 if(f[i]>g[j]) 34 { 35 result[i]++; 36 j++; 37 } 38 else 39 { 40 flag_i=1; 41 sum+=result[i]; 42 i++; 43 } 44 } 45 printf("sum is %d\n",sum); 46 for(i=0;i<len_f;i++) 47 printf("%d ",result[i]); 48 printf("\n"); 49 }
下面是从资料上找到的另外一种方法，代码非常少。思路与我的很相似，也是因为两个数组都从小到大排序好了，那么，当f[i]>g[j]，那么，在f中就一定有len_f-i个元素大于g[j]了。
1 void count() 2 { 3 int i=0,j=0; 4 while(i<len_f && j<len_g) 5 { 6 if(f[i]<=g[j]) 7 i++; 8 else 9 sum+=len_f-i,j++; 10 } 11 }
如果您觉得我的文章对您有帮助，请赞一下，非常感谢。
本文转自NeilHappy 51CTO博客，原文链接：http://blog.51cto.com/neilhappy/1099686，如需转载请自行联系原作者
