题目描述：有m层的楼，一部电梯，电梯只能停到一层，然后里面的人走到自己所在层。

一个人上N层，他的不满意度为N * a 0.5 * N * (N - 1)

一个人下N层，他的不满意度为N * b 0.5 * N * (N - 1)

给你每层的人数，问你在第几层停下，可以使总的不满意度最小？

解题报告：

m^2的复杂度会超时，所以需要推导公式。

如果电梯停在ans层。某人在下面，在第i层。需要下N = (ans - i）层

他的不满意度为：N * b 0.5 * N * (N - 1)

如果电梯停在ans 1层，这个人的不满意度为（N 1) * b 0.5 * (N 1) * (N)

 = N * b 0.5 * N * (N - 1) b N.

多出了b和N。

同样，上楼也是。所以找到了递推关系。

设sum[i]，为从第一层到第i层一共多少人。

up[i]表示电梯停在i层，i层以上的所有人一共需要爬的层数。

则有 up[i] = up[i 1] (sum[m] - sum[i]);

同理，down[i] = sum[i - 1] down[i - 1];

ansUp[i]为电梯停在i层，i层以上的所有人不满意度的和。

ansUp[i] = ansUp[i 1] up[i 1] a * (sum[m] - sum[i]);

其中up[i 1] a * (sum[m] - sum[i]);就是多出来的N和a的和。

同理，ansDown[i] = ansDown[i - 1] down[i - 1] b * sum[i - 1];

代码不长，如下：

#include<iostream>
using namespace std;
#define size 10004
int t, m, a, b, x[size], id;
__int64 ansUp[size], ansDown[size], ans, up[size], down[size], sum[size];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &m, &a, &b);
        ansDown[0] = ansUp[m] = down[0] = sum[0] = up[m] = sum[m] = 0;
        for(int i = 1; i <= m; i )
            scanf("%d", &x[i]), sum[i] = sum[i - 1] x[i];
        for(int i = 1; i <= m; i )
        {
            down[i] = sum[i - 1] down[i - 1];
            ansDown[i] = ansDown[i - 1] down[i - 1] b * sum[i - 1];
        }
        for(int i = m - 1; i >= 1; i--)
        {
            up[i] = up[i 1] (sum[m] - sum[i]);
            ansUp[i] = ansUp[i 1] up[i 1] a * (sum[m] - sum[i]);
        }
        id = 1 ,ans = ansUp[1] ansDown[1];
        for(int i = 2; i <= m; i )
            if (ansUp[i] ansDown[i] < ans)
                ans = ansUp[i] ansDown[i], id = i;
        printf("%d\n", id);
    }
    return 0;
}