1843.圆形牛棚

Powered by:NEFU AB-IN

Link

文章目录

• 1843.圆形牛棚
• • 题意
  • 思路
  • 代码

1843.圆形牛棚

• 题意

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

• 思路

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

• 代码

  '''
  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 = INFfor i in range(n):tmp = (n - 1) * sumk = (n - 1)for j in range(i, n):tmp -= (k * A[j])k -= 1for j in range(0, i - 1):tmp -= (k * A[j])k -= 1res = min(res, tmp)print(res)
  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！