304572: CF870B. Maximum of Maximums of Minimums
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Maximum of Maximums of Minimums
题意翻译
题目描述 给你一个数组 a1,a2...an,还有一个整数n和整数k。 你必须把这堆数组恰好分成k个非空数组。然后,计算每个子数组上对最小整数,并取k个最小值中的最大整数。 你能得到最大的整数是什么? 子数组和分开数组的定义在说明给出。 输入格式 第一行 n,k (1 <= k <= n <= 1e+5 ) (n是数组长度,k是分成的子数组数) 第二行包括n个整数 a1,a2,a3...an (-1e+9 <= ax <= 1e+9) 输出格数 输出一个整数,表示可以获得的最大整数,如果将原数组拆成k个非空子数组。 说明 一个数组a的子数组[l,r] 是 al,al+1,...ar 将数组分成k个子数组[l1,r1],[l2,r2]...[lk,rk] (l1 = 1, rk = n, li = ri+1) 一共k个子数组(意思就是切成了k个小数组) 在第一个样例中,你应该将数列分割为数组【1,2,3,4]和5的数组,表示[1,4] 和[5,5]。最小值为min(5)=1,min(5)=5、结果的最大值max(1,5) = 5。显然易见地,这是最佳答案。 在第二个样例中,你唯一的选择就是把这个数组分成(-4 -5 -3 -2 -1)的一个子数组[1,5]。唯一的最小值为min(-4,-5,-3,-2,-1)=-5,最小值的结果是-5。 感谢@Himself65 @paizhang 提供的翻译题目描述
You are given an array $ a_{1},a_{2},...,a_{n} $ 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<=10^{5} $ ) — the size of the array $ a $ and the number of subsegments you have to split the array to. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ -10^{9}<=a_{i}<=10^{9} $ ).
输出格式
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