f820 - 極限運動 (Sports)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個整數陣列，以及一個起始索引 t。目標是找到陣列中，從起始索引 t 出發，向左或向右移動，直到遇到一個比當前位置值更小的值時停止的位置。如果向左或向右移動遇到相同的值，則繼續移動。最後輸出停止位置的索引。

解題思路

這個問題可以使用貪心演算法解決。首先，比較起始位置的左右鄰居的值。如果左鄰居大於右鄰居，則向左移動，直到遇到比當前位置值更小的值。反之，如果右鄰居大於左鄰居，則向右移動，直到遇到比當前位置值更小的值。在移動過程中，如果遇到與當前位置值相同的值，則繼續移動。為了避免邊界問題，在陣列的頭部和尾部添加了哨兵值 100001。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int a[32],n,t,tmp;
int main(){
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> a[i];
	cin >> t;
	tmp = a[t];
	a[0]=a[n+1]=100001;
	if(a[t+1]>a[t-1])
		while(a[t]>=a[t-1])
			--t;
	else
		while(a[t]>=a[t+1])
			++t;
	cout << t;
}