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: