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;
}
评论