找到一個滿足約束條件的數字

我有兩個數字P和K。我有一個的 N整數。我想找到最小數A[i]，只是滿足屬性abs(A[i]-P) <= K其中0 <= i < N。給予A排序。找到一個滿足約束條件的數字

最初，我想到了O(N)的方法。但我認爲它可以通過使用二進制搜索來優化到O(logN)。但我不知道如何繼續下去。

2015-06-21 user3186829

這是正在進行的編程競賽：https：//www.hackerrank.com/contests/epiccode/challenges/dance-in-pairs –

對不起，我沒有意識到這個事實。我會在比賽結束後澄清我的疑問實際上，我的疑問是，參考這個問題「https://www.hackerrank.com/contests/infinitum-jul14/challenges/sherlock-and-probability」 – user3186829

有一個社論爲這個挑戰。你可以閱讀它，我很懷疑這裏的某個人寫的答案比編輯中寫的更詳細。 –

使用此：

for(i=0; i<=n; i++)pre[i]=0; 
    for(i=1; i<=n; i++) 
    { 
      pre[i]=pre[i-1]; 
      if(s[i-1]=='1')pre[i]++; 
    } 
    for(i=1; i<=n; i++) 
    { 
      if(s[i-1]=='0')continue; 
      ans += pre[min(n,i+k)]-pre[max(0ll,i-k-1)]; 
    } 
    LL gc=gcd(ans,n*n); 
    cout << ans/gc << "/" << (n*n)/gc << endl;

來源

2015-06-21 11:00:41 Nakshatra

嘗試以下邏輯：

查找最小數量指標，使用>= abs(P-K)二進制搜索，如果沒有找到去，
查找最小數索引<= (P+K)使用二進制搜索，如果沒有找到，那麼就沒有這樣的數字。

這是O(log(n))我想。

來源

2015-06-21 12:20:57

找到一個滿足約束條件的數字

回答

相關問題