P1733 DVD服务请求

    • 95通过
    • 485提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 快速排序,快排 排序 搜索 贪心
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    gloria正在管理一个DVD库,假定有k台DVD播放机,用户可以通过这些播放机查看自己想要的DVD内容。一台播放机一次只能放一张DVD,当一个客户请求播放一张DVD时,如果这张DVD已经在一台DVD机里面,则不需要进行任何操作,否则就需要把这张DVD插入一台空播放机中,如果所有播放机都不为空,gloria就需要选择一台播放机,先把里面的DVD拿出来,再放入需要的DVD,gloria不是个好动的人,她想使DVD的插入操作次数尽可能少。

    假定请求序列x1, x2, . . . , xn 已经预先给定,gloria必须先处理排在前面的请求。显然问题的关键在于当一个请求来到,而没有播放机空闲的时候gloria要选择取出哪张DVD。如k=2,请求序列为1, 2, 3, 1, 3, 1, 3对于前面两个请求,直接把DVD 1和2放入播放机中,当第3个请求到达时,gloria有两种选择:

    (1) 把DVD 1取出,再把DVD 3插入,则对于请求4-7,gloria至少还需要一次DVD插入;

    (2) 把DVD 2取出,再把DVD 3插入,则对于请求4-7,gloria不再需要DVD插入操作。

    显然选择2比1更优。

    给定k和请求序列,你能帮gloria求出需要最少的DVD插入数目吗?

    输入输出格式

    输入格式:

    每组测试数据第一行包括两个整数k(1<=k<=10,1<=n<=100),接下来n行,每行一个整数表示一个DVD请求,第i行表示请求xi(1<=xi<=100)。

    输出格式:

    对于每组测试数据,输出一行包括一个整数表示需要的最少的插入操作。

    输入输出样例

    输入样例#1: 复制
    2 7
    1
    2
    3
    1
    3
    1
    3
    
    输出样例#1: 复制
    3
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。