上得厅堂。下得厨房。写得代码。翻得围墙。欢迎来到睿不可挡的每日一小练！

题目：支配值数目

内容：已知f[]和g[]两个整数数组。元素都已经从小到大排列。试编敲代码算出f[]中每个元素比g[]中每个元素大的个数的总数。

换句话说。f[0]比g[]中多少个元素大、f[1]比g[]中多少个元素大。这些值得总和就是所要求的答案。

比如，假设f[]中有1,3,5,7,9，而g[]中有2,4,6,7,8，比g[0]大的有f[1]~f[4],比g[1]大的有f[2]~f[4],比g[2]大的有f[2]~f[4],比g[3]大的是f[4],比g[4]大的是f[4]，因此答案是4+3+3+1+1=12.

我的解法：上来没多想，打开vs2013就敲了起来。问题果然非常easy，分分钟就超神。

。

奥，不正确就攻克了。

#include 
     
      using namespace std;int _tmain(int argc, _TCHAR* argv[]){	int f[5] = { 1, 3, 5, 7, 9 };	int g[5] = { 2, 4, 6, 7, 8 };	int length = 0;	int sum = 0;	for (int i = 0; i < 5; i++)	{		for (int j = 0; j < 5;j++)		{			if (g[i] < f[j])				length++;					}		sum += length;		length = 0;	}	cout << sum << endl;	getchar();	return 0;}
     

实验结果

只是我的解法的时间复杂度是n²我自己也认为不好，然后我又细致的想了想，最终想出来一个n的算法。

#include 
     
      using namespace std;int _tmain(int argc, _TCHAR* argv[]){	int f[5] = { 1, 3, 5, 7, 9 };	int g[5] = { 2, 4, 6, 7, 8 };	int index_f = 0;	int index_g = 0;			int sum = 0;	while (index_f < 5 && index_g < 5)	{		if (g[index_g] >= f[index_f])			index_f++;		else		{			sum += (5 - index_f);			index_g++;		}	}	cout << sum << endl;	getchar();	return 0;}
     

实验结果

嘿嘿！

每天练一练。日久见功夫，加油！

              -End-

參考文献：《c语言名题精选百则》