5．士兵站队 题目：训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排成一行，依次编号为1，2，…，n。 第i个士兵的身高H(i)，由于采用特殊单位，H(i)满足1≤H(i)≤2000000000。 设第i个士兵右侧最近的比他个高的士兵编号为j，则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。（不考虑客观因素，比如视力范围等-,-） 求S(1)+S(2)+…+S(n)。 输入： 标准输入。 第一行为整数n，表示士兵的个数。 第二行n个整数，用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高 输出： S(1)+S(2)+…+S(n)的结果 例： 输入 6 10 3 7 4 12 2 输出 5 主函数： #include <iostream> #include <time.h> using namespace std; int Sum(int h[], int n); int main(void) { time_t startTime; time_t endTime; const int n = 50000; int h[n] = {0}; int temp, p; //获取互不相同的一组数列 for (int i=0; i<n; i++) h[i] = i + 1; for (int i=n-1; i>0; i--)//洗牌，使得数的大小随机排列 { p = rand()%i; temp = h[i]; h[i] = h[p]; h[p] = temp; } //计时 time(&startTime); int s; for (int i=1; i<10000; i++) s = Sum(h, i); time(&endTime); cout << "sum = " << s << endl; cout << "time = " << difftime(endTime, startTime) << endl; system("pause"); return 0; } 方法一：根据题意可以得到一个很简单的算法，那就是遍历数组，依次累计每个元素右边比它小的元素，直到遇到比它大的元素为止。算法是时间复杂度为O（n^2）。 int Sum(int h[], int n) { int sum = 0; for (int i=0; i<n; i++) { for (int j=i+1; h[j]<h[i] && j<n; j++) sum++; } return sum; } 或者 int Sum(int h[], int n) { int i, j; int sum = 0; for (i=0; i<n; i++)//从左到右遍历每一个士兵 { for (j=i+1; h[j]<h[i] && j<n; j++)//累计士兵右边比他矮的人数 ; sum += j - i - 1;//累积总人数 } return sum; } 方法二：一个分治算法，思路和方法一一样，都是遍历数组，求出每一个S(i)，然后相加，区别在于不是从左到右依次计算，而是以当前的最高人为中心，分别计算其左右两边的人。算法是时间复杂度为O（n^2）。 int F(int h[], int low, int high) { int i; for (i=low+1; h[i]<h[low] && i<high; i++)//累计士兵右边比他矮的人数 ; int sum = i - low - 1; if (i > low + 1) sum += F(h, low+1, i); if (i < high-1) sum += F(h, i, high); return sum; } int Sum(int h[], int n) { F(h, 0, n); } 方法三：以空间换时间，设置一个临时数组来存储原数组中的递减序列，依次将原数组中的元素与序列中元素比较，看是否可以将其插入到序列中。插入的法则为：若h[i] > temp[0]，即下一个士兵高度大于序列中任一高度，则用h[i]覆盖原序列中的所有元素，即top = 0;若h[i] < temp[top]，即下一个士兵高度小于序列中任一高度，这样只要将h[i]插入到序列的尾部，即++top;若不是上述两种情况，即h[i]只比序列中的一部分元素大，这样只要用h[i]覆盖原序列中的比它小的元素，我们在序列中找到h[i]的插入位置就可以了。最后更新序列的元素，并累积序列的长度。这样时间复杂度可以降低到O（n）。 这里借鉴了http://www.programfan.com/club/的yxs0001的代码，表示感谢！ int Insert(int h[], int n, int x)//二分法求插入的位置 { int low = 0, high = n; int m; while (low <= high)//确保插入的位置是在low处，循环体最终总是执行low = m + 1; { m = (low + high) / 2; if (h[m] > x) low = m + 1; else high = m - 1; } return low; } int Sum(int h[], int n) { int *temp = new int[n];//设置一个临时数组来存储原数组中的递减序列 int top = 0;//临时数组栈顶 int sum = 0; int i; temp[top] = h[0]; for (i=1; i<n; i++) { if (h[i] > temp[0])//下一个士兵高度大于序列中任一高度 top = 0; else if (h[i] < temp[top])//下一个士兵高度小于序列中任一高度 ++top; else //下一个士兵高度在序列中将其插入序列 top = Insert(temp, top, h[i]); temp[top] = h[i]; sum += top; } delete []temp; return sum; } 另外，http://www.programfan.com/club/的Kummerwu也写了一个很有趣的代码，他设置了一个结构，需要更多的空间，但是代码也更好理解，更高效。而且Kummerwu是一个很幽默的人，他幽默的注释，给程序带来了不少生趣。 typedef struct taller { int h; /* 第一个比自己高的士兵的身高 */ int pos; /* 该士兵的位置 */ }TALLER; //说白了，就是一个出栈，入栈的过程，每个元素入栈一次，在入栈的过程中， //可以将比自己小的元素踢出栈，所以最坏情况下，所有元素入栈，出栈各操作一次 //故复杂度为O(n) int Sum(int h[], int n) { const int MAX_SOLDIER_CNT = 50000; const int MAX_SOLDIER_H = 2000000000; static TALLER talls[MAX_SOLDIER_CNT + 2]; //高个子俱乐部 TALLER * cur_tall = talls; int count = 0; cur_tall->h = MAX_SOLDIER_H + 1; //标兵(靠，这家伙还真高呀) cur_tall->pos = n; for (n-=2; n>=0; n--) { //如果我比右侧的那个家伙高(俺也算个高个子了) if (h[n] > h[n+1]) { //把比自己矮的士兵踢出栈,(呵呵，爽! ) while (cur_tall->h < h[n]) { cur_tall--; //这里可能有优化的空间??可以用二分法插入 } //算算中间有几个矮冬瓜(现在cur_tall是第一个比我高的家伙) count += cur_tall->pos - n - 1; //呵呵，俺光荣的加入高个子俱乐部了 :). cur_tall++; cur_tall->h = h[n]; cur_tall->pos = n; } //靠，右侧那家伙比我高 //(算了，让他进入高个子堆吧,反正也没啥油水可以捞) else { cur_tall++; cur_tall->h = h[n+1]; cur_tall->pos = n+1; } } return count; }
评论