/*
电梯调度算法:
微软有6部电梯，每层都有人上下，电梯在每层都停。
每次电梯从一层往上走时，只允许电梯停在其中的某一层。所有的乘客都从一楼上电梯，到达某层后，电梯停下来，
所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则自动计算出应停在
的楼层。
电梯停在那一层，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。
分析:本质是优化问题。如何寻找抽象模型。树?图?
影响结果的两个因素：乘客数目及需要停的目的楼层。我们可以从统计到达各层的乘客数目分析；
假设楼层一共有N层，电梯停在第x层，要去第i层的乘客数目总数为Tot[i],这样所爬楼梯的总数就是
从1到N 对Tot[i]*|i-x|求和
我们只需要找到x即可
解法1:
可以从第一层开始枚举x一直到N层，计算出总共要爬的层数，然后选取最小值。每层楼计算时，要把所有N层楼计算
一遍，时间复杂度为O(n)，总共计算N层楼，因此总时间复杂度为O(n^2)
解法2:
假设电梯停在第i层楼，可以计算出所有乘客总共要爬楼梯的层数Y，如果有N1个乘客的目的楼层在i层楼一下，有N2
个乘客在第i层楼，还有N3个乘客再第i层楼以上。这个时候，如果电梯改停在第i-1层，所有目的地在第i-1层及
以下的乘客可以少爬一层，总共可以少爬N1层，而目的地在第i层及以上的乘客需要多爬一层，总共多爬N2+N3层
乘客总共需要爬的层数为Y-N1+(N2 + N3) = Y - (N1 - N2 - N3)
反之，如果电梯在i+1层停，乘客需要爬的层数为Y+N1+N2-N3
停i-1:Y - N1 + N2 + N3,当N1 > N2 + N3时，停在第i-1层好，乘客少走N1-N2-N3
停i+1:Y - N3 + N1 + N2，当N1 + N2 < N3时，停在第i+1层好，
其他情况：停在第i层好
我们从第一层开始考察，计算各位乘客需要爬的数目，然后调整，时间复杂度降为O(N)
输入:
5(电梯层数，接下来有n行，第i行的数字表示第i层有多少人想停在这一楼,电梯标号默认从1开始，如果有多层相同，就输入标号最小的)
3 5 8 9 4
4
20 2 3 4
4
10 2 8 4
输出:(第几层电梯,以及需要怕露底的数目)
3 28
1 20
2 26
分析:
第一层停的话，那么第二层的人要走的层数:5,第三层:2*8,四:3*9,五:4*4 ，一共 = 5 + 16 + 27 + 16 = 64
第二层停:一:3,三:8，四:2*9,五:3*4 =,共 = 3 + 8 + 18 + 12 = 41
第三层停:一:2*3,二:5,四:9,五:2*4,一共 = 6 + 5 + 9 + 8 = 28
第四层停:共= 3*3 + 2 *5 + 1*8 + 4*1 = 9 + 10 + 8 + 4 = 31
第五层停:共= 4*3 + 3*5 + 2*8 + 1*9 = 12 + 15 + 16 + 9 = 52
*/
/*
关键:
1 假设电梯停在第i层楼，可以计算出所有乘客总共要爬楼梯的层数Y，如果有N1个乘客的目的楼层在i层楼一下，有N2
个乘客在第i层楼，还有N3个乘客再第i层楼以上。这个时候，如果电梯改停在第i-1层，所有目的地在第i-1层及
以下的乘客可以少爬一层，总共可以少爬N1层，而目的地在第i层及以上的乘客需要多爬一层，总共多爬N2+N3层
乘客总共需要爬的层数为Y-N1+(N2 + N3) = Y - (N1 - N2 - N3)
反之，如果电梯在i+1层停，乘客需要爬的层数为Y+N1+N2-N3
停i-1:Y - N1 + N2 + N3,当N1 > N2 + N3时，停在第i-1层好，乘客少走N1-N2-N3
停i+1:Y - N3 + N1 + N2，当N1 + N2 < N3时，停在第i+1层好，
其他情况：停在第i层好
我们从第一层开始考察，计算各位乘客需要爬的数目，然后调整，时间复杂度降为O(N)
2 for(i = 2,n1 = 0 ,n2 = pArr[1] , n3 = 0; i <= iLen ; i++)
//用第一层开始对第1层下面，第一层，第一层上面的人数赋值
{
n3 += pArr[i];
iMin += pArr[i]*(i-1);
}
3 //需要向上一层楼梯遍历的情况是:第i-1层和第i层都需要加走的步数需要累加:N1+N2，而第i层以上
//减少步数为:N3,如果N3> N1 + N2,此时应向上走
if(n3 > n1 + n2)
{
iMin -= (n3 - n1 - n2);
n1 += n2;
n3 -= pArr[i];//这里必须减去当前层数
*/
#include <stdio.h>
#include <iostream>
using namespace std;
const int INT = 0x7fffffff;
const int MAXSIZE = 10000;
int abs(int n)
{
return n > 0 ? n : -1*n;
}
pair<int,int> elevatorAssign(int* pArr,int iLen)
{
int iMin = INT;
int iMinIndex = -1;
int iSum;
for(int i = 1 ; i <= iLen ; i++)
{
iSum = 0;
for(int j = 1 ; j <= iLen ; j++)
{
iSum += pArr[j]*abs(i - j);
}
if(iSum < iMin)
{
iMin = iSum;
iMinIndex = i;
}
}
return make_pair<int,int>(iMinIndex,iMin);
}
pair<int,int> elevatorAssign_optimized(int* pArr,int iLen)
{
int n1,n2,n3,i;
int iMin = 0;
for(i = 2,n1 = 0 ,n2 = pArr[1] , n3 = 0; i <= iLen ; i++)
//用第一层开始对第1层下面，第一层，第一层上面的人数赋值
{
n3 += pArr[i];
iMin += pArr[i]*(i-1);
}
for(i = 2 ; i <= iLen ; i++)
{
//需要向上一层楼梯遍历的情况是:第i-1层和第i层都需要加走的步数需要累加:N1+N2，而第i层以上
//减少步数为:N3,如果N3> N1 + N2,此时应向上走
if(n3 > n1 + n2)
{
iMin -= (n3 - n1 - n2);
n1 += n2;
n3 -= pArr[i];//这里必须减去当前层数
n2 = pArr[i];
}
else
{
break;
}
}
return make_pair<int,int>(i-1,iMin);
}
void process()
{
int n;
while(EOF != scanf("%d",&n))
{
if(n <= 0)
{
break;
}
int iArr[MAXSIZE];
for(int i = 1 ; i <= n ; i++)
{
scanf("%d",&iArr[i]);
}
//pair<int,int> pairRes = elevatorAssign(iArr,n);
pair<int,int> pairRes = elevatorAssign_optimized(iArr,n);
printf("%d %d\n",pairRes.first,pairRes.second);
}
}
int main(int argc,char* argv[])
{
process();
getchar();
return 0;
}