Technocup B (CODEFORCES)

問題概要

• \(N\) 要素の配列 \( a_1, a_2, ... a_N \) を \(K\) 個に分割する。
• \(K\) 個に分割されたそれぞれの要素の最小値のうち、最大になるものを求めよ。

制約

• \( 1 \leq K \leq N \leq 10^{5}\)
• \( -10^{9} \leq a_i \leq 10^{9} \)

問題はこちら

考えたこと

Kの値が 1, 2, 3以上 で取り扱いが異なる。

K == 1 の時

この時、配列 \(a\) の最小値が答えになる。

K == 2 の時

この時、次の場合のどちらかしかありえない

• \([1, 1], [2, N]\) に分割される時
• \([1, N-1], [N, N]\) に分割される時

そのため、配列の最初と最後の要素のうち、大きい方が答えとなる。

K >= 3 の時

この時、 配列の最大値の要素, その前の要素群, その後の要素群 に必ず分割することができるため、配列の最大値 が答えとなる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1<<30;

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int N, K; cin >> N >> K;
  vector<int> a(N);
  int minn=inf, maxn = -inf;
  for(int i = 0; i < N; ++i) {
    cin >> a[i];
    minn = min(minn, a[i]);
    maxn = max(maxn, a[i]);
  }
  if(K==1) cout << minn << endl;
  else if(K == 2) cout << max(a[0], a[N-1]) << endl;
  else cout << maxn << endl;

  return 0;
}