程式設計之美之小飛的電梯排程算法

原題解法二有問題，隻有證明使N1 + N2 >= N3成立的第一個i值就是全局最優解"，才能保證給出的代碼的正确性。如果證明不了，就要周遊一遍，時間複雜度仍未o(n)

//============================================================================

// Name : 程式設計之美之小飛的電梯排程算法.cpp

// Author :

// Version :

// Copyright : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================

#include <iostream>

using namespace std;

int n;

int person[100];

const int MAX=100000;

void compute(int &sum,int &Target)

{

int N1,N2,N3=0;

N2=person[1];

N1=0;

sum=0;

Target=1;

for(int i=2;i<=n;i++)

{

N3+=person[i];

sum+=(i-1)*person[i];

}

for(int i=2;i<=n;i++)

{

if(N1+N2<N3)

{

sum+=N1+N2-N3;

Target=i;

N1+=N2;

N2=person[i];

N3-=person[i];

}

else

//break;

continue;

}

}

//擴充問題1

void compute(int &sum,int &Target,int k)

{

int N1,N2,N3=0;

N1=0;

N2=person[1];

sum=0;

Target=1;

for(int i=2;i<=n;i++)

{

N3+=person[i];

sum+=(i-1)*person[i];

}

for(int i=2;i<=n;i++)

{

if(k*(N1+N2)<N3)

{

sum+=k*(N1+N2)-N3;

Target=i;

N1+=person[i-1];

N2=person[i];

N3-=person[i];

}

else continue;

}

}

int main() {

person[1]=2;

person[2]=3;

person[3]=4;

person[4]=6;

person[5]=2;

person[6]=2;

n=6;

int sum;

int Target;

compute(sum,Target,1);

cout << sum<<" "<<Target << endl;

return 0;

}