1701.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
long per[10000],total,go;
_int64 up,down,d1,d2,best;
_int64 a,b,m;


int main()
{int i,t,t1,t2,t3;
cin>>t;

while(t--)
{cin>>t1>>t2>>t3;
m=t1;a=t2;b=t3;
up=0;down=0;d1=0;

for(i=0;i<m;i++)
{cin>>per[i];
if(i)per[i]+=per[i-1];
down+=((m-1-i)*b+(m-1-i)*(m-1-i-1)/2)*(per[i]-(i==0?0:per[i-1]));
if(i<m-1)d1+=(b+m-2-i)*(per[i]-(i==0?0:per[i-1]));
}


total=per[m-1];
d2=a*(per[m-1]-per[m-2]);
best=down+up;go=t1-1;

for(i=t1-2;i>=0;i--)
{down-=d1;if(i)d1-=per[i-1]+b*(per[i]-per[i-1]);
 up+=d2;d2+=total-per[i]+a*(per[i]-per[i-1]);
 if(best>down+up){best=down+up;go=i;}
}

cout<<go+1<<endl;
}
return 0;
}