最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 问题 AT: L17-5 单调队列优化dp1 - 作业

    正文概述 网友投稿   2026-01-22 16:13:51  

    题目描述

    中心塔有一个博物馆,游客众多。博物馆有一个很奇怪的规定,就是在购买门票时必须说明两个数字,a 和 b,代表他要看展览中的第 a 幅至第 b 幅画(包含 a 和 b)之间的所有图画,而门票的价钱就是一张图画一元。 为了看到更多名师的画,小机器人希望入场后可以看到所有名师的画(至少各一张),但也想只花费最少的钱。 下面请你编程帮助小机器人,写一个程序决定他购买门票时的 a 值和 b 值。

    输入

    输入包括两行。 第一行包含两个整数 N 和 M,表示图画总数和画家数量。(N ≤ 10^6,M <= 2000) 第二行包含 N 个整数,它们都介于 1 和 M 之间,代表画作作者的编号。

    输出

    输出两个整数 a 和 b。 数据保证有解,如果存在多个解,则输出 a 最小的那个解。

    样例输入

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

    样例输出

    2 7

    提示

    本题中,滑动窗口的存在周期是,当前入队元素,与队列中元素有相同的,队列头不断后移,直到队列头部元素不重复。
    信息学奥赛网,一个优质的源码资源平台!
    信息学奥赛网 » 问题 AT: L17-5 单调队列优化dp1 - 作业