CF870B.Maximum of Maximums of Minimums
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a1,a2,...,an consisting of n integers, and an integer k . You have to split the array into exactly k non-empty subsegments. You'll then compute the minimum integer on each subsegment, and take the maximum integer over the k obtained minimums. What is the maximum possible integer you can get?
Definitions of subsegment and array splitting are given in notes.
输入格式
The first line contains two integers n and k ( 1<=k<=n<=105 ) — the size of the array a and the number of subsegments you have to split the array to.
The second line contains n integers a1,a2,...,an ( −109<=ai<=109 ).
输出格式
Print single integer — the maximum possible integer you can get if you split the array into k non-empty subsegments and take maximum of minimums on the subsegments.
输入输出样例
输入#1
5 2 1 2 3 4 5
输出#1
5
输入#2
5 1 -4 -5 -3 -2 -1
输出#2
-5
说明/提示
A subsegment [l,r] ( l<=r ) of array a is the sequence al,al+1,...,ar .
Splitting of array a of n elements into k subsegments [l1,r1] , [l2,r2] , ..., [lk,rk] ( l1=1 , rk=n , li=ri−1+1 for all i>1 ) is k sequences (al1,...,ar1),...,(alk,...,ark) .
In the first example you should split the array into subsegments [1,4] and [5,5] that results in sequences (1,2,3,4) and (5) . The minimums are min(1,2,3,4)=1 and min(5)=5 . The resulting maximum is max(1,5)=5 . It is obvious that you can't reach greater result.
In the second example the only option you have is to split the array into one subsegment [1,5] , that results in one sequence (−4,−5,−3,−2,−1) . The only minimum is min(−4,−5,−3,−2,−1)=−5 . The resulting maximum is −5 .