算法: 前缀和 & 推公式
思路:
题目要求求出最小总距离,因此我们可以使用前缀和的方法。但是这道题的难点在于如何求各种开门方式对应各牛棚所耗费的时间.
我们可以先把各种情况列出来,如图所示
可以发现每个数字经过位移后的数字与右移次数和本身有关,经过计算后可以得出结论,变换后的数字为(右移次数 + 本身数字 - 1) % 最大数。这里模最大数是防止有超过最大数的情况。
题中所给的数据范围为3 - 1000 所以我们把时间复杂度控制在O(n^2logn)就好。
时间复杂度:
O(n^2)
代码
#include<iostream>
using namespace std;
const int N = 1010,inf = 99999999;
int t[N][N], q[N], n, res = inf;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &q[i]);
for(int i = 1; i <= n; i ++) //这里i表示右移次数 + 1;
for(int j = 1; j <= n; j ++) //j表示本身数字
{
t[i][j] = t[i][j - 1] + q[j] * ((i + j - 2) % n);//这里减二是因为奶牛走到自己
//的房间距离为两房间距离之差
if(j == n) res = min(res, t[i][j]);
}
return cout << res, 0;
}