h660 - 躲避球 (DodgeBall)

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個躲避球的遊戲情境。初始時，玩家位於一個位置 ans。有多個球以不同的速度 s 從不同的位置 x 投擲過來。玩家可以移動到球的位置，如果球的速度小於或等於玩家的速度 v。如果球的速度大於玩家的速度，玩家會向左或向右移動一段距離（15），具體方向取決於球的位置與玩家的位置關係。目標是計算玩家最終的位置。

解題思路

這題的解題思路是模擬躲避球的過程。對於每一個投擲過來的球，判斷球的位置是否在玩家的躲避範圍內（距離小於等於 d）。如果在躲避範圍內，再判斷球的速度是否小於等於玩家的速度。如果球的速度小於等於玩家的速度，則玩家移動到球的位置。如果球的速度大於玩家的速度，則玩家根據球的位置向左或向右移動 15 個單位。最終，玩家的位置就是答案。

複雜度分析

• 時間複雜度: O(b)，其中 b 是投擲球的數量。因為程式碼需要遍歷每一個球。
• 空間複雜度: O(1)，程式碼只使用了常數個變數。

程式碼

#include <iostream>
using namespace std;
int ans,d,v,b,x,s;
int main(){
	cin >> ans >> d >> v >> b;
	for(int i=0;i<b;++i){
		cin >> x >> s;
		if(abs(ans-x)<=d){
			if(s<=v){
				ans=x;
			}
			else{
				if(x>=ans){
					ans-=15;
				}
				else{
					ans+=15;
				}
			}
		}
	}
	cout << ans;
}