挡板长度
测试数据来自 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