摘要
Title: 1843. 圆形牛棚
Tag: 模拟、前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1843. 圆形牛棚

• 题意

  作为当代建筑的爱好者，农夫约翰建造了一个完美圆环形状的新牛棚。
  牛棚内部有 n 个房间，围成一个环形，按顺时针编号为 1∼n。
  每个房间都既有通向相邻两个房间的门，也有通向牛棚外部的门。
  约翰想让第 i 个房间内恰好有 ri 头牛。
  为了让奶牛们有序的进入牛棚，他计划打开一个外门，让牛从该门进入。
  然后，每头牛顺时针穿过房间，直到到达合适的房间为止。
  约翰希望通过合理选择打开的门，使得所有奶牛的行走距离之和尽可能小（这里只考虑每头牛进入牛棚以后的行走距离）。
  请确定他的奶牛需要行走的最小总距离。

• 思路

  $O(n^2)$都能过，所以就直接模拟了

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-01-26 13:16:29
  FilePath: \ACM\Acwing\1843.py
  LastEditTime: 2022-01-26 13:22:43
  '''
  
  A = []
  INF = int(4e9)
  
  if __name__ == "__main__":
      n = int(input())
      for i in range(n):
          A.append(int(input()))
      sum = sum(A)
      res = INF
      for i in range(n):
          tmp = (n - 1) * sum
          k = (n - 1)
          for j in range(i, n):
              tmp -= (k * A[j])
              k -= 1
          for j in range(0, i - 1):
              tmp -= (k * A[j])
              k -= 1
          res = min(res, tmp)
      print(res)