P3650 [USACO1.3]滑雪课程设计Ski Course Design

    • 1.8K通过
    • 3.3K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 搜索 枚举,暴力 概率论,统计 模拟 贪心 USACO
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    农民约翰的农场里有N座山峰(1<=N<=1000),每座山都有一个在0到100之间的整数的海拔高度。在冬天,因为山上有丰富的积雪,约翰经常开办滑雪训练营。

    不幸的是,约翰刚刚得知税法在滑雪训练营方面有新变化,明年开始实施。在仔细阅读法律后,他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于17就要收税。因此,如果他改变山峰的高度(使最高与最低的山峰海拔高度差不超过17),约翰可以避免支付税收。

    如果改变一座山x单位的高度成本是x^2单位,约翰最少需要付多少钱?约翰只愿意改变整数单位的高度。

    输入输出格式

    输入格式:

    第一行:一个整数n

    第二行到N+1行:每行是一座山的海拔高度

    输出格式:

    约翰需要支付修改山海拔高度的总金额,最高和最低的山峰间高度差最多17。

    输入输出样例

    输入样例#1: 复制
    5
    20
    4
    1
    24
    21
    输出样例#1: 复制
    18

    说明

    约翰保持高度为4、20和21的山的高度。他增高高度为1的山、变成高度4(花费 3 ^ 2 = 9)。他降低了高度为24的山变成高度21也花费3 ^ 2 = 9。

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。