TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1095
  • 题目
  • P1095气球游戏
    限制 : 时间限制 : 15000 MS   空间限制 : 65536 KB
    问题描述

    何老板在磁器口摆摊提供打气球游戏。就是在一大块布上挂满各种颜色的小气球,游客可以花钱购买气枪子弹,然后用何老板提供的气枪在远处射击气球。
    何老板提供了一种奖励,就是如果在连续T枪中打爆了所有颜色的气球,将得到一只泰迪熊作为奖励。(注意:不是所有的气球,而是所有颜色的气球,也就是每种颜色的气球至少被打爆一只)
    总共有m种不同颜色的气球,编号1到m。一个游客买了n发子弹,然后连续开了n枪。何老板想知道在这n枪中,游客打爆所有颜色的气球,最少用了连续几枪?

    输入格式

    第一行两个空格间隔的整数数n,m。
    第二行一共n个空格间隔的整数,分别表示每一枪打中的气球的颜色,0表示没打中任何颜色的气球。

    输出格式

    就一个整数,表示游客打爆所有颜色气球用的最少枪数。如果游客无法在这n枪打爆所有颜色的气球,则输出-1

    样例输入 1

    12 5
    2 5 3 1 3 2 4 1 0 5 4 3

    样例输出 1

    6

    样例输入 2

    14 5 
    2 5 3 1 3 2 4 1 0 5 4 3 2 1

    样例输出 2

    5

    提示

    30% n<=1000 m<=20。
    100% n<=1000000 m<=2000。

    样例1解释:有五种颜色的气球,编号1到5。游客从第2枪开始直到第7枪,这连续六枪打爆了 5 3 1 3 2 4这几种颜色的气球,包含了从1到5所有的颜色,所以最少枪数为6。