小飞的电梯调度法

134 阅读 0 评论 89 点赞

我是靠谱客的博主粗犷牛排，这篇文章主要介绍小飞的电梯调度法，现在分享给大家，希望可以做个参考。

小飞的电梯调度法

问题主要就是逐一从下往上查询，若人第i层，继续往上到i+1 层时，若满足N1+N2”<”N3**(这个地方我是没明白为什么一写<，后面的东西就莫名消失了，所以给<加了引号)*，则第*i+1 层更好。当在这个条件不再满足时，分为两种情况，若N1+N2=N3，则i+1 层和i 层同样好。若N1+N2>N3时，则选择停留在i 层更好。这个算法的时间复杂度将为0(N)。
每一个人要停在的楼层数字

代码如下：

复制代码

#include<fstream>
#include<iostream>
#include<stdlib.h>
using namespace std;

#define N 10
int nperson[N]={0};
void init()
{
    ifstream file("louceng.txt");
    int a;
    while(file!=NULL)
    {
        file>>a;
        //cout<<a<<endl;
        nperson[a]+=1;
    }
    for(int i=0;i<10;i++)
        cout<<"第"<<i<<"层人数: "<<nperson[i]<<endl;
    file.close();
}
int main()
{
    init();
    int minFloor=0; 
    int N1,N2,N3;
    int targetFloor=1;
    int j;
    int count=0;
    for (N1=0,N2=nperson[1],N3=0,j=2;j<=N;j++)
    {
        N3+=nperson[j];
        minFloor+=nperson[j]*(j-1);
    }
    //cout<<N3<<endl;
    for(j=2;j<=N;j++)
    {
        if(N1+N2<N3)
        {
            count++;
            //cout<<N2<<endl;
            minFloor=minFloor+N1+N2-N3;
            N1+=N2;
            N2=nperson[j];
            N3-=nperson[j];
        }
        else
        {
            targetFloor=j-1;
            break;
        }
    }
    cout<<"目标楼层： "<<targetFloor<<endl<<"最小爬楼数： "<<minFloor<<endl;
    //return 0;
    system("pause");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<fstream>
#include<iostream>
#include<stdlib.h>
using namespace std;

#define N 10
int nperson[N]={0};
void init()
{
    ifstream file("louceng.txt");
    int a;
    while(file!=NULL)
    {
        file>>a;
        //cout<<a<<endl;
        nperson[a]+=1;
    }
    for(int i=0;i<10;i++)
        cout<<"第"<<i<<"层人数: "<<nperson[i]<<endl;
    file.close();
}
int main()
{
    init();
    int minFloor=0; 
    int N1,N2,N3;
    int targetFloor=1;
    int j;
    int count=0;
    for (N1=0,N2=nperson[1],N3=0,j=2;j<=N;j++)
    {
        N3+=nperson[j];
        minFloor+=nperson[j]*(j-1);
    }
    //cout<<N3<<endl;
    for(j=2;j<=N;j++)
    {
        if(N1+N2<N3)
        {
            count++;
            //cout<<N2<<endl;
            minFloor=minFloor+N1+N2-N3;
            N1+=N2;
            N2=nperson[j];
            N3-=nperson[j];
        }
        else
        {
            targetFloor=j-1;
            break;
        }
    }
    cout<<"目标楼层： "<<targetFloor<<endl<<"最小爬楼数： "<<minFloor<<endl;
    //return 0;
    system("pause");
}

执行结果

代码中用到了创建了一个ifstream类的对象，由于类构造函数本身具有和成员函数open()一样的功能，可以打开文件，所以直接ifstream file(“.txt”)就可以打开文件了。
我在编译的时候碰见一个问题就是文件名字写错了，结果程序执行直接跳过打开文件这步，搞得我花了一点时间才弄明白咋回事。
我从别的那里摘来了一点关于文件操作的介绍：[(http://soft.chinabyte.com/database/460/11433960.shtml)]