JOI 予選 2009 B - コンテスト (AOJ 0533) (6Q, 難易度 2)

ソートの練習問題

• 問題へのリンク

問題概要

20 個の整数が与えられる。

• 前半 10 個の整数のうち、大きい順に 3 個の整数の総和
• 後半 10 個の整数のうち、大きい順に 3 個の整数の総和

をそれぞれ求めよ。

解法

前半ができれば後半も同様なので、前半を考えます。

10 個の整数のうち大きい順に 3 個の和をとるのは、次のようにできます。

---

1. 10 個の整数を大きい順に並び替える
2. 並び替えた状態で前から 3 個の和を求める

---

1 については、C++ であればソート関数 sort() が使えます。デフォルトでは小さい順に並び替えるので、大きい順に並び替えるためには greater を指定するとよいでしょう。

具体的には、vector<int> 型変数 A を大きい順に並び替えるのは次のように書けます。

sort(A.begin(), A.end(), greater<int>());

コード

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

// 配列 A の上位 3 個の和を求める関数
int calc(vector<int> A) {
    sort(A.begin(), A.end(), greater<int>());
    return A[0] + A[1] + A[2];
}

int main() {
    vector<int> A(10), B(10);
    for (int i = 0; i < 10; i++) cin >> A[i];
    for (int i = 0; i < 10; i++) cin >> B[i];
    cout << calc(A) << " " << calc(B) << endl;
}