C++之练习题1

68 阅读 0 评论 45 点赞

我是靠谱客的博主欣喜鸡，最近开发中收集的这篇文章主要介绍C++之练习题1，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.某公司大厦一共有6部电梯。在高峰时期，每层都有人上下，电梯在每层都停。老总常常会被每层都停的电梯弄得很不耐烦，于是他提出了如下办法：

由于楼层不太高，那么在上下班时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有的乘客都从一楼上电梯，到达某层楼后电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则自动计算出应停的楼层。

问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？

分析：
假设楼层共有N层，电梯停在第x层，要去第i层的乘客数目为Tot[i]，这样爬楼梯的总数就是

因此就是要找到一个整数x，使得上述值最小

int nPerson[]; //到达第i层的乘客数目
int i,j,nFloor, nMinFloor, nTargetFloor;
nTargetFloor = -1;
for (i = 1 ; i <= N; i++){
nFloor = 0;
for (j = 1 ; j < i; j++)
nFloor += nPerson[j] * (i - j);
for (j = i+1 ; j <= N; j++)
nFloor += nPerson[j] * (j - i);
if (nTargetFloor == -1 || nMinFloor > nFloor){
nMinFloor = nFloor;
nTargetFloor = I;
}
}
return (nTargetFloor, nMinFloor);

分析：
        假设电梯停在i层，则可以计算出所有乘客总共要爬楼梯的层数Y。其中：有N1个乘客目的楼层在第i层以下，有N2个乘客目的楼层在第i层，还有N3个乘客目的楼层在第i层以上。
        若此时电梯停在i-1层，则所有目的地在i层及以上的乘客都要多爬一层，总共需多爬N2+N3层，而所有目的地在第i-1层及以下的乘客可以少爬1层，总共可以少爬N1层。因此乘客总共需要爬的楼层数为Y-N1+N2+N3= Y – (N1-N2-N3)
        反之，若电梯停在i+1层，则乘客总共需要爬的楼层数为Y+ (N1+N2-N3)
        因此，当N1>N2+N3时，电梯厅在i-1层更好，乘客可以少爬(N1-N2-N3)层楼；而当N1+N2<N3时，电梯厅在i+1层更好;其他情况下，电梯厅在第i层更好。
       根据这个策略，可以从第1层开始考察，计算各乘客需要爬楼梯的数目，然后根据上述策略进行调整下横，知道找到最佳楼层

int nPerson[]; //到达第i层的乘客数目
int nMinFloor, nTargetFloor;
int N1, N2, N3;
nTargetFloor = -1;
nMinFloor = 0;
int i = 0;
for (N1 = 0, N2 = nPerson[1], N3 = 0; i = 2; i <= N; i++){
N3 += nPerson[i];
nMinFloor += nPerson[i] * (i - 1);
}
for (i = 2; i <=N; i++){
if (N1 + N2 < N3) {
nTargetFloor = i;
nMinFloor += (N1 + N2 - N3) ;
N1 += N2;
N2 = nPerson[i];
N3 -= nPerson[i];
}
else
break;
}
return (nTargetFloor, nMinFloor);