【AtCoder】ABC 352 C - Standing On The Shoulders | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 136

問題概要

の名前が付いた 人の巨人がおり、巨人 の肩の高さは , 頭の高さは である。これから以下の規則に従って 人の巨人を積み上げていくことを考える。一番上に立っている巨人の、地面を基準とした頭の高さとして実現できる最大値を求めよ。

規則 :

• まず、任意に巨人を1人選び地面に立たせる。
• 次に、一番上の巨人の肩の上に次の巨人を立たせる。これを 回繰り返す。

制約

• 入力はすべて整数。
• 
• 

考察

直感的に考えると、「頭と肩の高さの差が小さい巨人から積み上げていくことで、次の巨人を肩に乗せるときの無駄を減らしていきたい」という貪欲的なアイデアが思い浮かぶ。

この直感は実は正しい。最終的な高さは、巨人 が最上部にいるとして で計算できるが、ここで の部分は によらない値になることから、結局は を最大化したいことになる。公式解説ではこれを全探索によって求めていたが、私の場合は先にソートして求めてしまった。

具体的には、 と そのインデックス をペアにしてpairに突っ込み、前者で昇順ソートするというものである。

あとはループを回して計算していこう。

コード

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using Pair_int = pair<int, int>;

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> A(N + 1), B(N + 1);
    rep(i, 1, N + 1) cin >> A[i] >> B[i];

    vector<Pair_int> diff(N + 1);
    rep(i, 1, N + 1) diff[i] = make_pair(B[i] - A[i], i);
    sort(all(diff));

    ll ans = 0;
    rep(i, 1, N + 1)
    {
        if (i == N)
            ans += B[diff[i].second];
        else
            ans += A[diff[i].second];
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 15分