1.暴力代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 1005; int m, n; int r[maxn]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> r[i]; } int ans = 0; int min=0; for (int i = 0; i < n; i++)//从第i个房间进入 { int all = 0; if(i==0){//min存i=0时的数据 for(int j=0;j<n;j++){ all+=r[j]*j; } min=all; ans=all; } else{ for(int j=i;j<n;j++){//i~n all+=r[j]*(j-i); } for(int j=0;j<i;j++){//0~i-1 all+=r[j]*(j+n-i); } if(min>all){ min=all; ans=min; } } } cout<<ans; }
2.数学方法：
当从第一个房间开始进入： ans=0·r1+1·r2+......+(n-1)·rn
当从第二个房间开始进入： ans=(n-1)·r1+0·r2+......+(n-2)·rn
容易发现，当顺时针一次改变时，ans就是先减掉一个sum（r1+r2+r3+…+rn）再加上n·rk,k为前一个门的编号
代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 1005; int m, n; int r[maxn]; int main() { cin >> n; int all = 0; // 存r1+r2+r3+...+rn for (int i = 1; i <= n; i++) { cin >> r[i]; all += r[i]; } int min = 0; int sum = 0; for (int i = 1; i <= n; i++) // 从第i个房间进入 { if (i == 1) { // 算第一个的作为初始的sum for (int j = 1; j <= n; j++) { sum += r[j] * (j - 1); } min = sum; } else { sum -= all; // 先减r1+r2+...+rn sum += n * r[i - 1]; // 再+n*r[i-1] if (min > sum) { min = sum; } } } cout << min; }
