找到一个满足约束条件的数字
问题描述:
我有两个数字P
和K
。我有一个的 N
整数。我想找到最小数A[i]
,只是满足属性abs(A[i]-P) <= K
其中0 <= i < N
。 给予A
排序。找到一个满足约束条件的数字
最初,我想到了O(N)
的方法。但我认为它可以通过使用二进制搜索来优化到O(logN)
。但我不知道如何继续下去。
答
使用此:
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;
答
尝试以下逻辑:
- 查找最小数量指标,使用
>= abs(P-K)
二进制搜索,如果没有找到去, - 查找最小数索引
<= (P+K)
使用二进制搜索,如果没有找到,那么就没有这样的数字。
这是O(log(n))
我想。
这是正在进行的编程竞赛:https://www.hackerrank.com/contests/epiccode/challenges/dance-in-pairs –
对不起,我没有意识到这个事实。我会在比赛结束后澄清我的疑问实际上,我的疑问是,参考这个问题“https://www.hackerrank.com/contests/infinitum-jul14/challenges/sherlock-and-probability” – user3186829
有一个社论为这个挑战。你可以阅读它,我很怀疑这里的某个人写的答案比编辑中写的更详细。 –