挡板长度

测试数据来自 system/1757

作业已超过截止时间,您无法递交本题目。

时间限制: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

贪心算法练习题(一)

未认领
状态
已结束
题目
11
开始时间
2024-01-18 00:00
截止时间
2024-03-01 23:59
可延期
24.0 小时