AOJ ITP2 3_B（Min-Max Element）を解く

Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の3_B問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#3では、列に対する操作を学びます。

#3から#6は、alogrithm をインクルードして利用する機能を紹介します。全てのアルゴリズムは、データ構造の実装から切り離されています。アルゴリズムの要件（主にイテレータ）を満たせば動作します。

問題（3_B: Min-Max Element）

問題はリンク先をご覧ください。

AOJ ITP2 3_B問題: Min-Max Element

イテレータ範囲から最小値を求める min_element と最大値を求める max_element について学びます。

std::min_element, std::max_element について

以下は、cpprefjp 様の記事（min_element, max_element）を参考にさせていただきました。

std::min_element は、最小値を取得します。std::max_element は、最大値を取得します。どちらもイテレータで範囲を指定します。

  template <class ForwardIterator>
  ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
  ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

先頭から、last – first – 1 回比較します。

C++ プログラム例（ITP2 3_B）

与えられた数列とクエリが与えられます。クエリは、読み込んだ先頭の数字が ０ か １ の2種類あります。

• 0 b_i e_i: [b, e) の最小値を出力する。
• 1 b_i e_i: [b, e) の最大値を出力する。

与えられたクエリに対して、min_element と max_element を呼び出します。以下は、C++のプログラムです。

#include <iostream>
#include <algorithm>

#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		int b, e;
		cin >> b >> e;
		int ans;
		if (command == 0) {
			ans = *min_element(a.begin() + b, a.begin() + e);
		} else if (command == 1) {
			ans = *max_element(a.begin() + b, a.begin() + e);
		}
		cout << ans << endl;
	}

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

min_element や max_element は使ったことがありませんでした。C++11 から min と max で複数要素が指定できるようになりました（記事参照）。使い分けが出来ると良いのですが、忘れてしまいそうです。

引き続き、ITP2 の問題を紹介していきます。