TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3842
  • 题目
  • P3842监狱2
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 1000ms
    问题描述

    一个监狱,构造很奇特,有N个牢房,但是N个牢房却是一字排起的。第i个牢房紧挨着第i+1个(除了末尾那个),每个房间里都有一个囚犯。
    上级要求将某些罪犯释放,给了一份名单,名单里给出了每个要被释放囚犯的房间号。要求每天释放一个人。
    现在牢房中一共有N个人,他们互相之间可以传话,如果有一个人离开了,那么能和他说上话的人就会自闭,如果想让他们冷静下来,看守必须给自闭的人吃一只鸡腿。

    输入格式

    第一行两个数N和M,M表示要释放名单上的人数;

    第二行M个数,表示释放哪些人

    输出格式

    仅一行,表示最少要送多少只鸡腿

    样例输入 1

    20 3 
    3 6 14

    样例输出 1

    35

    样例输入 2

    100 5
    30 44 50 65 86

    样例输出 2

    247

    提示

    样例说明:
    先释放14号房间中的罪犯,1到13号可以相互传话,15到20号可以相互传话,但是[1,13]号与[15,20]号之间不能传话了,所以要给1到13号监狱和15到20号监狱中的19人送鸡腿吃;
    再释放6号房间中的罪犯,要给1到5号监狱和7到13号监狱中的12人送鸡腿;
    最后释放3号房间中的罪犯,要给1到2号监狱和4到5号监狱中的4人送鸡腿。

    数据范围

    对于 30%的数据,1≤N≤100;1≤M≤5。

    对于 70%的数据,1≤N≤1000; 1≤M≤100;

    对于100%的数据, 1≤N≤4000; 1≤M≤100;