#PU616. USACO 2016 February Contest, Bronze — Problem 2. Circular Barn

    ID: 1351 传统题 文件IO:cbarn 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:feb16来源:usaco.orgscoring:equal_test_cases枚举

USACO 2016 February Contest, Bronze — Problem 2. Circular Barn

USACO 2016 February Contest, Bronze — Problem 2. 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 nn rooms, numbered clockwise from 1…n1 \ldots n around the perimeter of the barn (3≤n≤1,0003 \leq n \leq 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 rir_i cows to end up in each room ii (1≤ri≤1001 \leq r_i \leq 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 nn. Each of the remaining nn lines contain r1…rnr_1 \ldots r_n.

输出格式

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

数据范围

(见题面原文)

样例

样例 1

5
4
7
8
6
4
48
In this example, the best solution is to let the cows enter through the
door of the room that requires 7 cows.
Problem credits: Brian Dean