- Today
- Total
Running Deeper C/C++/Java
Circular Barn (Gold) 성공
시간 제한메모리 제한제출정답맞은 사람정답 비율
| 2 초 | 512 MB | 91 | 44 | 37 | 52.113% |
문제
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≤100,000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.
Farmer John owns n cows, and he wants exactly one cow to end up in each room in the barn. However, the cows, being slightly confused, line up at haphazard doors, with possibly multiple cows lining up at the same door. Precisely ci cows line up outside the door to room i, so ∑ci=n.
To manage the process of herding the cows so that one cow ends up in each room, Farmer John wants to use the following approach: each cow enters at the door at which she initially lined up, then walks clockwise through the rooms until she reaches a suitable destination. Given that a cow walking through d doors consumes d2 energy, please determine the minimum amount of energy needed to distribute the cows so one ends up in each room.
입력
The first line of input contains n. Each of the remaining n lines contain c1…cn.
출력
Please write out the minimum amount of energy consumed by the cows.
Solution:
Using Greedy algorithm, you can prove that starting anywhere that the cows are fully consumed(placed in rooms) after 1 rotation gives the exact same value always. You can also prove that this is the maximum case, as (n+1)^2 is much larger than the rest. Thus, You can find the exact spot using O(n), by adding a[i]-1 to the total sum each time(prefix sum), and choosing the start point as 1 point after the minimum. Then, you can simply create a queue and drop off the cows as fast as you can, while picking up new cows each time. This is a O(n) algorithm.