HBC24108Badeline,语言题Circular Barn Revisited题解

水水月牙 算法基础篇 52 0
题库丰富多样,涵盖各个领域,全网最全C++题库,让您在练习中不断成长!
After the last debacle involving Farmer John's circular barn, one would think he had learned his lesson about non-traditional architecture. However, he thinks he can still make his circular barn function properly by allowing multiple cows into each room. To recap, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn . 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 room i . To herd the cows into the barn in an orderly fashion, he plans to unlock k exterior doors , allowing the cows to enter through only those doors. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior doors that will cause his cows to collectively walk a minimum total amount of distance after entering the barn . Please determine the minimum total distance his cows will need to walk, if he chooses the best k such doors to unlock.

After the last debacle involving Farmer John's circular barn, one would think he had learned his lesson about non-traditional architecture. However, he thinks he can still make his circular barn (from the preceding problem) function properly by allowing multiple cows into each room. To recap, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn (3≤n≤100). 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 room i (1≤ri≤1,000,000). To herd the cows into the barn in an orderly fashion, he plans to unlock k exterior doors (1≤k≤7), allowing the cows to enter through only those doors. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior doors that will cause his cows to collectively walk a minimum total amount of distance after entering the barn (they can initially line up however they like outside the k unlocked doors; this does not contribute to the total distance in question). Please determine the minimum total distance his cows will need to walk, if he chooses the best k such doors to unlock.

HBC24108Badeline,语言题Circular Barn Revisited题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断学习,不断挑战,才能在编程领域中脱颖而出!全网最全C++题库,助您成为编程高手!

标签: HBC24108Badeline 语言题Circular Barn Revisited题解