Official
A - Find Takahashi Editorial by mechanicalpenciI
最も高い橋を求めるためには、橋を一本目から順に見ていき、
それまでに見た橋の中で最も高い橋を覚えておけば良いです。
新しい橋を見るときには、今までに見たうちで最も高い橋と、
新しい橋の高さを比較して、高かった方を新しく覚えれば良いです。
そのようにして、全ての橋を見終わった後で、最も高い橋が答えとなります。
これは for 文と if 文 を用いて書く事ができます。
別解としては、それぞれの橋をそれ以外の全ての橋と比較する方針があります。こちらでも今回の問題では支障がありませんが、時間計算量は本解の方が良いため、本解の方針を覚えておくと良いと思います。
c++ による実装例 :
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
int h[101];
int ans;
cin >> n;
for(int i=1;i<=n;i++)cin>>h[i];
ans=1;
for(int i=2;i<=n;i++){
if(h[ans]<h[i])ans=i;
}
cout << ans <<endl;
return 0;
}
Python による実装例 :
n=int(input())
h=list(map(int, input().split()))
ans=1
for i in range(2,len(h)+1):
if(h[ans-1]<h[i-1]):
ans=i
print(ans)
posted:
last update: