P4870 [BalticOI 2009 Day1]甲虫

    • 33通过
    • 74提交
  • 题目提供者 alpha1022
  • 评测方式 云端评测
  • 标签 BalticOI
  • 难度 省选/NOI-
  • 时空限制 4000ms / 16MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    译自 BalticOI 2009 Day1 T1「Beetle

    有一只甲虫处于一根水平的树枝。因为他沉迷数学无法自拔,所以他觉得很像是在 $x$ 轴上。

    在同一根树枝上,还有 $n$ 滴露水。每滴露水占用 $m$ 个单位的水分。相对于甲虫的位置,他们的坐标分别是 $x_1,x_2,\dots,x_n$。

    显然,这一天将会骄阳似火。每过一个时间单位,就会有一个单位的水分从每一滴露水流失。这只甲虫受尽了烈阳的折磨,以至于每当它碰到一滴露水都能瞬间喝完。在每个时间单位中它能移动一个单位的距离。

    所以你要写一个程序,根据露水的坐标,计算出甲虫最多能喝到的水。

    输入输出格式

    输入格式:

    第一行,两个整数,$n$ 和 $m$。

    以下 $n$ 行,每行一个整数,表示露水的坐标 $x_1,x_2,\dots,x_n$。

    输出格式:

    输出一行,表示甲虫最多能喝到的水

    输入输出样例

    输入样例#1: 复制
    3 15
    6
    -3
    1
    输出样例#1: 复制
    25

    说明

    $0 \le n \le 300,1 \le m \le 1,000,000,-10,000 \le x_1,x_2,\dots,x_n \le 10,000,$ 对于所有 $i \ne j,x_i \ne x_j$。

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