/ Vijos / 题库 /

木板长度

木板长度

时间限制:1秒  内存限制:256M


【题目描述】

  养猪场的猪圈一个紧挨着另一个排成一行,每个猪圈的宽度都为 1。其中有些猪圈有猪,有些则没有。一场百年一遇的暴风雨把猪圈的挡风门吹飞了。场主必须尽快在猪圈之前竖立起新的木板,为猪遮风挡雨。

  市场上虽然可以提供任意长度的木板,但数量是有限的。

  现在给出能买到的买到的木板最大的数目 \(M\);猪圈的总数 \(S\);猪的总数 \(C\);以及这些猪所在的猪圈的编号(一个猪圈最多有一头猪),请你计算拦住所有有猪的猪圈所需木板的最小总长度。

【输入格式】

  第一行包含三个整数:\(M\),\(S\) 和 \(C\),其中猪圈依次编号为 \(1..S\)。
  接下来的 \(C\) 行,每行包含一个整数,表示有猪的的猪圈的编号。

【输出格式】

  单独的一行包含一个整数表示所需木板的最小总长度。

【输入输出样例】

 Input

3 20 7
2
3
7
10
11
13
18

 Output

10

【输入输出样例说明】

  有 20 个猪圈,其中有猪的是第 2,3,7,10,11,13,18 号猪圈,用3块木板遮挡有猪的圈,如下图,用一块长度为2的木板挡住2,3号猪圈;用一块长度为7的木板挡住7,10,11,13号猪圈,用一块长度为1的木板挡住18号猪圈,因此总长度为2+7+1=10。
说明

【数据限制】

  对于 \(100\%\) 的数据,\(1<M<50\),\(1 ≤ S ≤ 200\)。

【来源】

  Mr.he

信息

ID
1757
难度
(无)
分类
贪心 | 其他 | 排序动态规划 点击显示
标签
递交数
0
已通过
0
通过率
?
被复制
6
上传者