Question

一道C/C++程序编程题

一个建筑有M层。每层的房客数对应为K1，K2，K3...一天所有的房客一起坐电梯回家。电梯只能停在某一层。每个房客如果在电梯停后要上N层楼，其不满意度为N * a + 0.5 * N * (N - 1)；每个房客如果在电梯停后要下N层楼，其不满意度为N * b + 0.5 * N * (N - 1) ； 为使房客的满意度最低，电梯应停在哪一层？

输入格式：
第一行为一个数T（0<=T<=20），用来表示测试数据的组数。
后面是T个测试数据。测试数据的第一行为M(1 <= M <= 10000)，a,b(0 <= a, b <= 100)。测试数据的第二行为每层楼的房客数K1，K2，K3...

输出格式：
对每个测试数据输出单行的结果，表示电梯应该停在哪层

输入例子：
1
5 3 2
1 1 1 1 1

输出例子：
3

下面是本人的程序：
#include "stdio.h"
int main()
{
int a,b,c,n,m;
int i,j,q=0,q1=-1;
int n1,n2,n3;
int k[10005]={0},p[10005]={0};
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&m,&a,&b);
for(k[0]=0,j=1;j<=m;j++)
scanf("%d",&k[j]);
for(n1=1;n1<=m;n1++)//假设电梯停在n1楼
{
for(c=0,n2=1;n2<=m;n2++)//对n2层的人来计算满意度
{
if(n1==n2)continue;
else if(n1>n2)c+=k[n2]*(a*(n1-n2)+(n1-n2)*(n1-n2-1)/2);//停楼上
else if(n2>n1)c+=k[n2]*(b*(n2-n1)+(n2-n1)*(n2-n1-1)/2);//停楼下
}
p[n1]=c;
}
for(q=p[1],n3=2;n3<=m;n3++)
if(q>p[n3])q=p[n3],q1=n3;
printf("%d\n",q1);
}
return 1;
}
貌似程序是对的。问题在于，此程序运行太慢，超出了一秒（老师的要求）。希望大家帮忙改一改。用动态规划做的兄弟姐妹，我会有至少三十的加分。谢谢！
兄弟们啊,M值范围为一到万,不定这么大数组不行啊....我不想的
现在空间没问题,关系是时间耗得太多,二重一万的for循环啊

Answer 1

首先构造个M*M的方阵,其中每个元素表示该层每人相对于其他层的不满意度.先初始化这个方阵,由不满意度的表达式看,只需要构造一个下(上)的三角矩阵,而且对角线元素值都相等(主对角元是0),至于上(下)三角里面的元素可用差值关系求得.有了这个表,剩下的问题就是纯计算了
循环上没少多少,不过少了条件比较,你试试看行不行

Answer 2

建议你去专门的编程论坛求助

Answer 3

可以去
bbs.csdn.net
你的程序是够慢的定义的数组那么大!我没怎么看!等有时间的话研究以下