CF870B

HD0X · 2021-11-06 09:20:26 · 题解

传送门

题意

给出由 n 个整数组成的数列和整数。你需要将这个数列分为正好 k 个非空片段，然后计算每个片段中的最小数，最后得到这些最小数中的最大值。通过这些操作，你能得到的值最大是多少？

分析

我们分别考虑几种情况：

• k=1

一个片段只能选取最小数，在输出时排序再输出 a[1] 就可以啦。

• k>2

我们可以把最大的单独划分开，像上面一样在输出时排序输出 a[n] 就可以了。

• k=2

两个片段中，一个包含 a[1]，一个包含 a[n]。 我们只需要比较它们两个大小输出大的，因为： 想变大，则需在 a[2] 到 a[n-1] 中找到更大的，但更大不会被选上，所以不能更大。选更小的则变小了，什么用也木有。

代码

#include <bits/stdc++.h>
using namespace std;
long long n,k,a[100001];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    if(k==1)
    {
        sort(a+1,a+1+n);
        cout<<a[1];
    }
    else if(k>=3)
    {
        sort(a+1,a+1+n);
        cout<<a[n];
    }
    else
    {
        if(a[1]>=a[n])
        {
            cout<<a[1];
        }
        else
        {
            cout<<a[n];
        }
    }
    return 0;
}