POJ 1701

 /*
Every tenant went up N floors would make the dissatisfied degree rise N * a + 0.5 * N * (N - 1) degrees,
every tenant went down N floors would make the dissatisfied degree rise N * b + 0.5 * N * (N - 1) degrees. △= Dp+1 – Dp
= ∑1=<i<=p Ki*(b+p-i)) - ∑p<i<=n Ki*(a+i-p-1)
= ∑1=<i<=n Ki * i +(b+p)*∑1=<i<=p Ki - (a-p-1)∑p<i<=n Ki
*/ #include <iostream>
#define MAXN 10001
using namespace std; __int64 _m[MAXN+];
int k[MAXN+];
__int64 p_2[MAXN+];
__int64 p_3[MAXN+];
int k_1[MAXN];
int k_2[MAXN]; int main()
{
//freopen("acm.acm","r",stdin);
int test;
int n;
int i;
int j;
int p_1;
int a;
int b;
scanf("%d",&test);
while(test --)
{
scanf("%d",&n);
scanf("%d",&a);
scanf("%d",&b); for(i = ; i <= n; ++ i)
{
scanf("%d",&k[i]);
} for(i = ; i <= n; ++ i)
{
k_1[i] = k_2[i] = k[i];
} for(i = n-; i >=; -- i)
{
k_2[i] += k_2[i+];
} for(i = ; i <= n; ++i)
{
k_1[i] += k_1[i-];
} p_1 = ;
for(i = ; i <= n; ++ i)
{
p_1 += k[i]*i;
} for(i = ; i <= n; ++ i)
{
p_2[i] = (b + i)*k_1[i];
} for(i = ; i <= n; ++ i)
{
k_2[i] -= k[i];
} copy(k_2,k_2+n+,p_3); for(i = ; i <= n; ++ i)
{
p_3[i] *= (a-i-);
}
_m[] = ;
for(i = ; i <= n; ++ i)
{
_m[] += (i-)*a+((i-)*(i-)/);
} for(i = ; i <= n; ++ i)
{
_m[i] = _m[i-] - p_1 + p_2[i-] - p_3[i-];
} __int64 min = ; int place; for(i = ; i <= n; ++ i)
{
if(_m[i] < min)
{
min = _m[i];
place = i;
}
}
cout<<place<<endl;
}
}

关注我的公众号,当然,如果你对Java, Scala, Python等技术经验,以及编程日记,感兴趣的话。

POJ 1701

技术网站地址: vmfor.com

上一篇:【Hybrid App】Hybrid App开发实战


下一篇:poj2409