背包问题贪心算法时间复杂度 求解一贪心算法问题

求解一贪心算法问题  

最快回答那个不懂别乱说，别误人子弟。

这题标准的贪心算法，甚至很多时候被当做贪心例题

要求平均等待时间，那么就得用 总等待时间 / 人数

所以只用关心总等待时间，

如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。

给你写了个，自己看吧。

#include "stdafx.h"

#include <iostream>

#include <algorithm>

#include <stdio.h>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n;

float arr[105];

cin >> n;

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

cin >> arr[i];

sort(arr, arr+n);

int tnow = 0;

int tmax = 0;

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

{

tmax += tnow;

tnow += arr[i];

}

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

{

printf("%0.2f ", arr[i]);

}

cout << endl;

printf("%0.2fn",tmax / (float)n);

return 0;

}