n686 - pA. 訊號傳遞

🔗 前往 ZeroJudge 原題

題目描述

題目描述了訊號傳遞問題，給定 N 個基地台的位置和訊號傳送範圍，要求計算從最左側基地台發出的訊號，向右最遠可以傳遞到的位置。

解題思路

此題可以使用貪心策略解決。從最左側基地台開始，每次更新訊號可以到達的最遠距離。對於每個基地台，檢查其是否在目前訊號到達範圍內。如果在範圍內，則更新訊號可以到達的最遠距離為該基地台位置加上其訊號傳送範圍。如果訊號到達範圍覆蓋了所有基地台，則輸出最後更新的最遠距離。程式碼中，ma 變數追蹤目前訊號可以到達的最遠距離。迴圈遍歷每個基地台，如果當前基地台的位置大於 ma，則表示訊號已經無法到達該基地台，直接輸出當前的 ma 值。否則，更新 ma 為 max(ma, a[i] + d)，其中 a[i] 是基地台位置，d 是基地台的訊號傳送範圍。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int a[1001],ma,n,d;
int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        if(a[i]>ma){
            cout << ma;
            return 0;
        }
        cin >> d;
        ma=max(ma,a[i]+d);
    }
    cout << ma;
    return 0;
}