# [Gold III] Nicest view [문제 링크](https://www.acmicpc.net/problem/31486) ## 문제 설명 <p>Paris is so crowded with tourists during the Olympic games! You want to escape the city and go on a hike on a linear trail path. Every kilometre on that trail, including at start and end, is a milestone, on which is written the stone’s altitude. The slope between two consecutive stones is constant, and no two stones have the same altitude.</p> <p>Planning to come back with your friends, you try to identify the point of the hike at which you had the nicest view. The beauty of a point of view is defined as the distance (measured in kilometres) between your position and the previous position, on your hike, that was at the same altitude. If such a previous position fails to exist, it means that you can see the city and its smog, and the beauty of that view is zero.</p> <p>You have listed the altitudes of the milestones. What is the maximal beauty on your hike?</p> ## 입력 <p>The input consists of two lines. The first line contains a single integer $N$, which is the number of milestones on the trail path. The second line contains $N$ space-separated integers $H_1, H_2, \dots , H_N$; each integer $H_k$ is the altitude (measured in metres) of the $k$^th milestone on the path.</p> ## 출력 <p>The output should contain a single line, consisting of a single number $S$: the best beauty score on your hike. This number is written either as an integer or as an irreducible fraction $N/D$ for which $D \ge 2$; we recall that a fraction $N/D$ is irreducible when the greatest common divisor of $N$ and $D$ is $1$.</p> ## 풀이 스택에 h가 감소하도록 넣으면서 증가할 때마다 이전과 만나는 거리를 계산해주면 된다. 1 ~ N 경우와, N ~ 1 경우 두 가지 케이스를 탐색하는 경우 산의 꼭대기에서만 탐색해도 된다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll h[100'000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) cin >> h[i]; stack<ll> stk; ll res1=0, res2=1; for(ll i=0;i<n;i++) { while(!stk.empty() && h[stk.top()]<=h[i]) stk.pop(); if(!stk.empty()) { ll cur1 = (i-stk.top())*(h[stk.top()]-h[stk.top()+1]) - (h[stk.top()]-h[i]); ll cur2 = h[stk.top()]-h[stk.top()+1]; ll gcdVal = gcd(cur1, cur2); cur1/=gcdVal; cur2/=gcdVal; if(res1*cur2<cur1*res2) res1=cur1, res2=cur2; } stk.push(i); } stk = {}; for(ll i=n-1;i>=0;i--) { while(!stk.empty() && h[stk.top()]<=h[i]) stk.pop(); if(!stk.empty()) { ll cur1 = (stk.top()-i)*(h[stk.top()]-h[stk.top()-1]) - (h[stk.top()]-h[i]); ll cur2 = h[stk.top()]-h[stk.top()-1]; ll gcdVal = gcd(cur1, cur2); cur1/=gcdVal; cur2/=gcdVal; if(res1*cur2<cur1*res2) res1=cur1, res2=cur2; } stk.push(i); } if(!res1) cout << 0; else cout << res1 << '/' << res2; } ```