找到一个满足约束条件的数字

我有两个数字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

找到一个满足约束条件的数字

回答

相关问题