[JOI精進録] 難易度6「Relay」(JOIG2021/2022 春合宿A)

問題リンク

atcoder.jp

問題概要

人の人 ()がいて、それぞれに、が定められている。
この中から3人 ()を選び、を最小化してください。

解説

AC解法 (100/100点)

< < として選ぶことで2つのの最大値の和を最小化することができます。今後はこの制約で選ぶことを考えます。
を全探索します。
はが最小になる、はが最小になるを選ぶのが最適です。
これは累積minを使って前計算、クエリで求められ、全探索にかかるので全体でこの問題を解くことができました。

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,r(numeric_limits<int>::max()); cin >> n;
  vector<pair<int,int>> A(n); for (auto& [b,a]:A) cin >> a >> b;
  sort(A.begin(),A.end());
  vector<int> acc(n+1,r); for (int i(n-1);i > -1;--i) acc[i]=min(acc[i+1],A[i].first+A[i].second); int mn(A[0].second);
  for (int i(1);i < n-1;++i){
    r=min(r,A[i].first+A[i].second+mn+acc[i+1]);
    mn=min(mn,A[i].second);
  }
  cout << r << endl;
}

提出結果

atcoder.jp