Circular Barn

NC24038. Circular Barn

描述

Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn (3≤n≤1,000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.
Farmer John wants exactly ri cows to end up in each room i (1≤ri≤100). To herd the cows into the barn in an orderly fashion, he plans to unlock the exterior door of a single room, allowing the cows to enter through that door. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior door that will cause his cows to collectively walk a minimum total amount of distance. Please determine the minimum total distance his cows will need to walk, if he chooses the best such door to unlock. The distance walked by a single cow is the number of interior doors through which she passes.

输入描述

The first line of input contains n. Each of the remaining n lines contain r1…rn.

输出描述

Please write out the minimum total amount of distance the cows collectively need to travel.

示例1

输入:

输出:

说明:

In this example, the best solution is to let the cows enter through the door of the room that requires 7 cows.

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3(3.9) 解法, 执行用时: 322ms, 内存消耗: 2832K, 提交时间: 2020-12-19 16:26:58

n = int(input())
rooms = []
for i in range(n):
    rooms.append(int(input()))
weights = list(range(1, n))

res = float("inf")

for i in range(n):
    r = 0
    for j in range(n - 1):
        r += weights[j] * rooms[(i+j) % n]
        if res <= r:
            break
    res = min(res, r)
print(res)

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 620K, 提交时间: 2019-08-09 16:34:24

#include<bits/stdc++.h>
using namespace std;
int a[10001],n,sum=INT_MAX;
int main()
{
int n,s;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int p;
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=i;j<=i+n-1;j++)
ans=ans+a[j]*(j-i);
sum=min(ans,sum);
}
printf("%d",sum);
}

C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 504K, 提交时间: 2019-06-30 09:07:06

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,a[maxn],ans=0x7fffffff;
int main(){
cin>>n;
for(int i=0;i!=n;++i)
    cin>>a[i];
for(int i=0;i!=n;++i){
int sum=0;
for(int j=0;j!=n;++j)
    sum+=j*a[(i+j)%n];
    ans=min(ans,sum);
}
cout<<ans;
return 0;
}