算法练习：支配值数目

算法练习：支配值数目2015-02-15内容：已知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就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就解决了！

#include <iostream> 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 <iostream> 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; }

实验结果

From：csdn博客 birdlove1987_