Skip to content

1007: 二哥的金链

题目

题目描述

一个阳光明媚的周末,二哥出去游山玩水,然而粗心的二哥在路上把钱包弄丢了。傍晚时分二哥来到了一家小旅店,他翻便全身的口袋也没翻着多少钱,而他身上唯一值钱的就是一条漂亮的金链。这条金链散发着奇异的光泽,据说戴上它能保佑考试门门不挂,RP++。好心的老板很同情二哥的遭遇,同意二哥用这条金链来结帐。虽然二哥很舍不得这条金链,但是他必须用它来付一晚上的房钱了。

金链是环状的,一共有 N 节,老板的要价是 K 节。随便取下其中 K 节自然没问题,然而金链上每一节的 RP 值其实并不一样,有高有低,二哥自己非常清楚。另外二哥并不希望把整个金链都拆散了,他只愿意在这条环形的金链上切两刀,从而切下一段恰好为 K 节的金链给老板。因为 RP 值越高的节越稀有,因此他希望给老板的金链上最高的 RP 值最小。

输入格式

第一行两个整数 N 和 K,表示金项链有 N 节,老板要价 K 节。

第二行用空格隔开的N个正整数 a1...aN ,表示每一节金链的价值为多少。

输出格式

输出一个整数,表示二哥给老板的金链上最高的 RP 值最小多少。

样例输入

样例输入 1

5 2 1 2 3 4 5

样例输入 2

6 3 1 4 7 2 8 3

样例输出

样例输出 1

2

样例输出 2

4

数据范围

对40%的数据,$3 \leq N \leq 200$ ;

对70%的数据,$3 \leq N \leq 20000$;

对100%的数据,$ 3 \leq N \leq 200000, 0 < ai \leq 10^9 $。

数据规模较大,建议用scanf("%d", &a[i]);来读数据。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!