/*
* floorProblem.java
*
* Created on 2009年4月29日, 上午3:01
*
* 问题描述:《编程之美》之小飞的电梯调度算法。
* 假设电梯只在某一楼层停,然后乘客下电梯步行至各自目的楼层,求电梯应停在哪一层能使乘客步行的楼层数和最少。
* 假设楼层为N,最大载人数为M,应停层数为X,每位乘客目的楼层为Mi,Mr表示实际乘客数。
* (1)数学想法:楼层应该停在sum(Mi)/Mr,如果此数为整数,则即为所求,若此数非整数,则可以上下相邻整数分别
* 求和,然后比较优劣
* (2)计算机最笨算法:遍历每个楼层,求出停在每个楼层乘客步行楼层数和,然后求最少值
* (3)书中提供想法:由于(2)的算法复杂度高,所以考虑将其中一套循环提出改为加减比较以减少复杂度。
* 假设电梯停在i层,乘客步行层数和为Y,去i-1及其以下层M(i-1),去i层Mi,去i+1及其以上层M(i+1)
* 如果电梯停在i-1层,则和为Y-M(i-1)+M(i+1)+Mi=Y-(Mi-1 - Mi+1 - Mi),如果电梯停在i+1层,则和为
* Y-M(i+1)+M(i-1)+Mi = Y - (Mi+1 - Mi-1 - Mi)。如果M(i-1)>Mi+1 + Mi,则停在i-1层更好,如Mi+1>Mi-1 + Mi,
* 则停在i+1层更好,否则停在i层更好。
* 此题中楼层和最大载客数目都是可量化的,最大载客数目一般不超过20,楼层数目视具体情况2-几百不等。算法一二
* 以载客为中心,floors[]存的是每个乘客要去的目的楼层,而方法三则是以楼层数目为中心。如果楼层数目超过载客数目,
* 很明显以载客为中心会稍微减少些资源,反之,以楼层为中心会更优。而第三种方法若以载客为中心,
* 则需要手动统计到每层的乘客数,当然也可以全部提供这两种数据。
* passengers[]存的是到每层的乘客数量。
*
* 如果电梯会在k个楼层停,如何解决?我的想法是,先将楼层分成k组,然后每组应用停1层算法。如果刚好能分成等k
* 层,则此问题解决。如果分成等k组,还剩余m项,m<k,则将m项最少人数的层分给相邻的非最少人数的层所在的组。
*
* 忽略一般的错误处理,假设用户很细心。
*
*/
package elevator;
import java.util.logging.ConsoleHandler;
import java.math.RoundingMode;
/**
*
* @author ziteng@nkbbs.org
*/
public class floorProblem
{
private int pNum;
private int fNum;
/**
* Creates a new instance of floorProblem
*/
public floorProblem()
{
pNum = 0;
fNum = 0;
}
/**
* @param passengerNum 乘客数目
* @param floorNum 楼层数目
*/
public floorProblem(int passengerNum, int floorNum)
{
pNum = passengerNum;
fNum = floorNum;
}
/**
* @param floors[] 每个乘客对应的目的楼层
*/
public int mathFun(int floors[])
{
int sum = 0;
int i = 0;
for(i = 0; i < pNum; i++)
{
sum += floors[i];
}
int evg = (int)Math.floor((double)sum/(double)pNum);
if(sum%pNum == 0)
{
return evg;
}
else
{
sum = 0;
for(i = 0; i < pNum; i++)
{
if(floors[i] - evg > 0)
{
sum += floors[i] - evg;
}
else
{
sum += evg - floors[i];
}
}
int sum1 = 0;
for(i = 0; i < pNum; i++)
{
if(floors[i] - evg - 1 > 0)
{
sum1 += floors[i] - evg - 1;
}
else
{
sum1 += evg + 1 - floors[i];
}
}
if (sum > sum1)
return (evg + 1);
else
return evg;
}
}
public int simpleFun(int floors[])
{
int sum[] = new int[fNum];
int i = 0;
int j = 0;
int minSum = 0;
int minFloor = 1;
for(i = 0; i < fNum; i++)
{
sum[i] = 0;
}
for(i = 0; i < fNum; i++)
{
for(j = 0; j < pNum; j++)
{
if(floors[j] - i - 1 > 0)
{
sum[i] += floors[j] - i - 1;
}
else
{
sum[i] += i + 1 - floors[j];
}
}
if(i != 0)
{
if(sum[i] < minSum)
{
minSum = sum[i];
minFloor = i;
}
}
else
{
minSum = sum[i];
}
}
return minFloor;
}
/**
* @param passengers[] 每个楼层对应乘客数目
*/
public int complexFun(int passengers[])
{
int minFloor = 1;
int i = 0;
int N1 = 0;
int N2 = passengers[0];
int N3 = 0;
//int minSum = 0;
for(i = 1; i < fNum; i++)
{
N3 += passengers[i];
//minSum += i * passengers[i];
}
for(i = 1; i < fNum; i++)
{
if(N1 + N2 < N3)
{
N1 += N2;
N2 = passengers[i];
N3 -= passengers[i];
minFloor = i;
}
else
break;
}
return minFloor;
}
/**
* @param passengers[] 每个楼层对应乘客数目
* @param floornum 楼层的数目,确定passengers数组的大小
* @param firstnum 需要分析楼段的最低楼层数。
*/
public int complexFun(int passengers[], int floornum, int firstnum)
{
int minFloor = firstnum;
int i = 0;
int N1 = 0;
int N2 = passengers[firstnum];
int N3 = 0;
//int minSum = 0;
if(floornum == 1)
return firstnum;
for(i = firstnum; i < floornum + firstnum; i++)
{
N3 += passengers[i];
//minSum += i * passengers[i];
}
for(i = firstnum; i < floornum + firstnum; i++)
{
if(N1 + N2 < N3)
{
N1 += N2;
N2 = passengers[i];
N3 -= passengers[i];
minFloor = i;
}
else
break;
}
return minFloor;
}
/**
* @param passengers[] 每个楼层对应乘客数目
* @param k 电梯停留的此数
*/
public int complexFunK(int passengers[], int k)
{
int MAX = 30;
int i = 0;
int N1 = 0;
int N2 = passengers[0];
int N3 = 0;
int rNum = 0;
for(i = 0; i < fNum; i++)
{
if(passengers[i] > 0)
{
rNum++;
}
}
//如果允许停的次数大于用户需要去的楼层层数,则直接停就好
if(k >= rNum)
{
for(i = 0; i < fNum; i++)
{
if(passengers[i] > 0)
{
System.out.println(i);
}
}
return 0;
}
int blocknum = rNum/k;
//如果可以恰好等分为k组,则等分
if(rNum%k == 0)
{
rNum = 0;
int firstnum = 0;
for(i = 0; i < fNum; i++)
{
if(passengers[i] > 0)
{
rNum++;
}
if(rNum == blocknum)
{
System.out.println(complexFun(passengers, i - firstnum, firstnum));
rNum = 0;
firstnum = i;
}
}
}
else
{
//找出乘客人数最少的leftnum个楼层,记录到floorrecord中,并进行排序,从小到大
int leftnum = rNum % k;
int floorrecord[] = new int[leftnum];
int numrecord[] = new int[leftnum];
int tmp[] = new int[pNum];
int min = 0;
int minindex = 0;
for(i = 0; i < fNum; i++)
{
if(passengers[i] == 0)
{
tmp[i] = MAX;
}
else
{
tmp[i] = passengers[i];
}
}
for(i = 0; i < leftnum; i++)
{
min = MAX;
for(int j = 0; j < fNum; j++)
{
if(tmp[j] > 0)
{
if(tmp[j] < min)
{
min = tmp[j];
minindex = j;
}
}
}
tmp[minindex] = MAX;
floorrecord[i] = minindex;
}
sort(floorrecord, leftnum);
rNum = 0;
int firstnum = 0;
int minfloorindex = 0;
int kcount = 0;
//每个分组有blocknum个楼层,人数最少的楼层不参与统计而是就近并入相邻组
for(i = 0; i < fNum; i++)
{
if(passengers[i] > 0 && i != floorrecord[minfloorindex])
{
rNum++;
}
else if(i == floorrecord[minfloorindex])
{
minfloorindex++;
}
if(rNum == blocknum)
{
kcount++;
if(kcount == k)
{
System.out.println(complexFun(passengers, fNum - firstnum, firstnum)+1);
}
else
{
System.out.println(complexFun(passengers, i - firstnum + 1, firstnum)+1);
}
rNum = 0;
firstnum = i + 1;
}
}
}
return 0;
}
private void sort(int arr[], int num)
{
int temp = 0;
for(int i = 0; i < num; i++)
for(int j = i+1; j < num; j++)
{
if(arr[j] < arr[i])
{
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
floorProblem fp = new floorProblem(15, 8);
//值以日常生活称呼为主。
int floors[] = {2,2,3,3,3, 4,4,5,5,5, 5,6,7,7,8};
//passengers[0]表示去第一层的用户数,在从一楼开始楼梯上升过程中一般为0.其它类推
int passengers[] = {0,2,3,2,4,1,2,1};
System.out.println(fp.mathFun(floors));
//因为数组从0开始,所以转换成日常称呼需要+1
System.out.println(fp.simpleFun(floors)+1);
System.out.println(fp.complexFun(passengers)+1);
fp.complexFunK (passengers, 4);
}
}