题目详情题解（0）讨论（0）提交记录（0）

AT_arc098_c.[ARC098E] Range Minimum Queries

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你有一个长度为 nn 的整数序列 AA，以及一个整数 KK。你会进行 QQ 次操作，一次操作如下：

  • 选择序列中一个长度为 KK 的区间，并且删除区间中的最小元素。如果有多个，你可以选择任何一个。

现在，设 XX 是你删除了的元素中最大的一个，YY 是最小的一个，请找出在最优情况下，X−YX-Y 的最小值。

输入格式

请从标准输入中读入：
$ N $ $ K $ $ Q $
$ A_1 $ $ A_2 $ $ ... $ $ A_N $

输出格式

请输出 X−YX-Y 可能的最小值。

限制

  • 1≤K≤N≤20001\le K\le N\le 2000
  • 1≤Q≤N−K+11\le Q\le N-K+1
  • 1≤Ai≤1091\le A_i\le 10^9
  • 输入都是整数

输入输出样例

  • 输入#1

    5 3 2
4 3 1 5 2

    输出#1

    1

  • 输入#2

    10 1 6
1 1 2 3 5 8 13 21 34 55

    输出#2

    7

  • 输入#3

    11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

    输出#3

    451211184

输入解题思路，AI测评打分。不知道怎么写?

首页