C语言名题精选百则之支配值数目
文章目錄
支配值数目(GTCount)
已知f[]与g[]两个整数数组,元素已经从小到大排列,请写一个程序,算出f[]中比g[]元素大的对数。换句话说,f[0]比g[]中多少个元素大,f[1]比g[]中多少元素大等,这些值的总和就是要求的答案。
例如,如果f[]中有1,3,5,7,9,而g[]中有2,3,4,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
说明: 与问题1.1一样,需要特别注意数组f[]与g[]已经排序。如果问题1.1能够做出完美的解答,那么本题也不难,相似的方法就可以得到高效率的程序。
利用数组已经排好序的这个特性,可以写出高效的程序. 解答见gt_count.py