这题不能用倍增吗?

P2249 【深基13.例1】查找

Lysea @ 2023-07-06 15:52:41

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,k,l,r,t,a[N];
signed main(){
    scanf("%d%d",&n,&m);
    memset(a,-1,sizeof(a));
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(m--){
        scanf("%d",&k);
        l=r=1,t=n;
        while(r){
            if(a[l+r]<=k) l+=r,r=min(r<<1,t-l);
            else t=l+r-1,r>>=1;
        }
        while(a[l-1]==k) l--;
        if(a[l]==k) printf("%d ",l);
        else printf("-1 ");
    }
    return 0;
}

总是T掉第6个点。

是因为要查找的数都比较偏后吗?


by N_z_ @ 2023-07-06 15:58:36

@Sands_Of_Time 考察全一序列,你的

while(a[l-1]==k) l--;

需要调用 O(n) 次。


by Lysea @ 2023-07-06 16:01:27

@Nz woc,没注意到这个


by Lysea @ 2023-07-06 16:02:24

@Nz 那怎么解决这个问题啊?不会要再写一个倍增吧.......


by N_z_ @ 2023-07-06 16:03:12

@Sands_Of_Time 看上去,查 k-1 然后加 1 可能可以


by N_z_ @ 2023-07-06 16:04:18

@Nz 看上去不可以


by N_z_ @ 2023-07-06 16:05:47

@Sands_Of_Time 别急,事实上你可以选择把每个数 \times2,不是第一次出现的 +1,查询 \times2,虽然看上去这很奇怪。


by Lysea @ 2023-07-06 16:15:45

@Nz 谢谢dalao,已AC。

您奇怪的方法真好用QAQ!


|