#P2945. [USACO09MAR] Sand Castle S
[USACO09MAR] Sand Castle S
题目描述
农夫 John 建造了一座沙堡!像所有好的城堡一样,城墙上有垛口,那种由垛口(空隙)和垛堞(填充空间)组成的精巧图案;见下图。他的城堡墙上的 个垛堞被方便地编号为 到 ;垛堞 的高度为 ;他的垛堞高度常常不同,这与许多其他的不同。
他希望以以下方式修改城堡设计:他有一个从 到 的数字列表,并希望将垛堞的高度更改为这些高度 的某种顺序(不一定是给定的顺序或从数据派生的任何其他顺序)。
为此,他雇佣了一些牛工匠来增加和降低垛堞的高度。当然,工匠们要价很高。特别是,他们向 FJ 收取总共 每单位高度增加的钱和 每单位高度减少的钱。
FJ 想知道如果他选择最佳的高度排列,修改他的沙堡的最低可能成本是多少。答案保证适合 位有符号整数。
注意:大约 的测试数据将有 ,大约 将有 。
输入格式
输出包括 行。
第 行:三个用空格分隔的整数:, 和 。
第 行到第 行:第 行包含两个用空格分隔的整数: 和 。
输出格式
第 行:一个整数,重建城堡所需的最低成本。
3 6 5
3 1
1 2
1 2
11
提示
FJ 的城堡起始高度为 , 和 。他希望将它们的高度更改为 , 和 ,以某种顺序。增加一个单位高度的成本为 ,减少一个单位高度的成本为 。
FJ 将第一个垛堞的高度减少 ,成本为 (得到高度为 , 和 的垛堞)。然后他为第二个垛堞增加一个单位的高度,成本为 (得到高度为 , 和 的垛堞)。 (由 ChatGPT 4o 翻译)