はじめに
たなしょです。
今回も答えがわからずこちらのブログを参考にさせていただきました。
全くわかりませんでした。
問題文
長さ N の数列 A 1 , A 2 , . . . , A N が与えられます。 1 以上 N 以下の各整数 i に対し、次の問いに答えてください。
数列中の A i を除く N − 1 個の要素のうちの最大の値を求めよ。
制約
- 2≤N≤200000
- 1≤Ai≤200000 入力中のすべての値は整数である。
考え方
全くわからないので実装から読み解いていきます。
いざ実装
#include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; typedef pair<int, int> P; int main() { int N; cin >> N; vector<int> data(N); vector<int> data2(N); for (int i = 0; i < N; i++) { cin >> data[i]; data2[i] = data[i]; } sort(data2.begin(), data2.end(), greater<int>()); for (int i = 0; i < N; i++) { if (data[i] == data2[0]) { cout << data2[1] << endl; } else { cout << data2[0] << endl; } } }
コードを読み解く
#include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; typedef pair<int, int> P; int main() { int N; cin >> N; vector<int> data(N); vector<int> data2(N); for (int i = 0; i < N; i++) { cin >> data[i]; data2[i] = data[i]; }
余分あなものがついていますがここまでわかりました。 変数Nに配列の要素数を書いていき、vectorで可変長の配列を作成する。(流石に配列を2つ作るとは思いませんでしたが。。。) dataに値を代入してdata2にも値を代入してます。
sort(data2.begin(), data2.end(), greater<int>());
sortしてますね。greater
for (int i = 0; i < N; i++) { if (data[i] == data2[0]) { cout << data2[1] << endl; } else { cout << data2[0] << endl; } }
for文を回してdata[i]とdata20が等しい場合(Aiの場合)は2番目の最大値を出力(data2[1])、そうでなければ1番目の最大値を出力(data2[0])を出力すれば問題文の解をみたすことができますね。
最後に
スマートな回答でしたね。 コード読み解いていて途中で感動しました。
話は変わりますが最近残業続きで数学の勉強ができてません。。。つらいです。。。
最後まで読んでいただいてありがとうございました。 もしよろしければtwitterアカウント(@piklus100yen)もフォローしていただけると幸いです!