查找是否可以進行數據通信

-4

N個路由器在X軸上提供並且希望相互通信。如果路由器之間的距離小於或等於K，則一個路由器可以向另一個路由器發送消息。查找是否可以進行數據通信

給定P對路由器，要發送消息。我們需要用「Y」或「N」天氣該對之間的數據傳輸是可能的或不可行的。

注意：超過1個路由器可以在X軸上的同一個點上。

約束：

1 ≤ N, P ≤ 10^5 
0 ≤ Ai, K ≤ 10^9 
1 ≤ A, B ≤ N

所以我想對於每個查詢了一個非常有效的算法。

讓如果我們有5個路由器，K = 3和2次的查詢如下：

路由器的位置：= 0 3 8 5 12

查詢1：1 2

這裏答案是「Y」既在彼此

查詢的範圍2:1 3

這裏答案爲「Y」定義爲兩者在彼此對於對範圍（ 1，3）路由器1可以將消息發送到路由器2，路由器2可以將其發送到路由器4，它可以將其發送到路由器3。

來源

2014-07-04 user3786422

這可能是更好的數學交換。不知道這甚至是遠程編程問題。我說數學交換，因爲它可能是一個圖論問題。這是一個「計算機科學」問題，但我有一種感覺，這將被標記爲脫離主題。 – Tommy

@Tommy爲什麼要進行數學交換？它與更好更高效的算法相關 – user3786422

只需預先計算並存儲每個路由器的範圍。或者，你是否有內存限制？ –

首先映射路由器位置/距離：

List<int> Routers=new List<int>(); 

Routers.Add(0); 
//.... 
Routers.Add(12);

創建配對：

class Pairs 
{ 
int[2] Pair; 
} 

List<Pair> Pairings=new List<Pair>(); 


Pairings.Add({Routers.IndexOf(0),Routers.IndexOf(1)}); 
Pairings.Add({Routers.IndexOf(0),Routers.IndexOf(2)});

創建檢查方法：

落實ALG：

foreach (Pair p in Pairings) 
{ 
    if(CanCommunicate(p[0],p[1]) 
    return "Y";; 
    else 
    return "N"; 
}

代碼是在C#

來源

2014-07-04 17:38:56 apomene

對不起，請參閱我的編輯後的第二個查詢。 – user3786422

它沒有必要，他們需要直接溝通。所以請做更新您的答案 – user3786422

路由器是在x軸上，所以兩個路由器之間進行直接通話，如果它們之間的差值小於該邊界內，並且如果沒有間隙的兩個可以間接交談在它們之間的路徑上的路由器之間的x軸太大以至於消息無法通過。

因此，按照x軸上升的順序對路由器進行排序，然後按升序x的順序考慮它們，並將它們分解爲不包含太大差距的路由器。對運行進行編號，然後兩臺路由器可以進行通信，當且僅當它們都處於相同的編號運行時。

來源

2014-07-04 18:20:44 mcdowella

請解釋一些例子我沒有得到你的方法，它類似於帕特里夏Shanahan在他的答案正在討論的接近。請提供一些僞代碼 – user3786422

給定間接通信，我首先找到差距，沿x軸的地方，兩個相鄰路由器之間的距離太大，以便它們進行通信。

對於每個路由器，記錄下一個缺口的位置。將行結束作爲一個缺口。

當且僅當它們共享相同的下一個間隙時，兩臺路由器才能通信。

============================================== ==============================

Sort the list of routers in ascending x co-ordinate order 

Initialize integer groupIndex to 0. 

For each router in x co-ordinate order: 
    Mark it with the current groupIndex 
    If there is a next router and it is more than distance K away, increment groupIndex 

Two routers can communicate if, and only if, they are marked with the same groupIndex.

來源

2014-07-04 18:28:39

PLease用示例或一些僞代碼解釋 – user3786422

@ user3786422由於您認識到與另一個不同措辭的答案的相似性，因此您似乎理解了這個想法。 –

是啊......但不是100％清楚你想說什麼 – user3786422

查找是否可以進行數據通信

回答

相關問題