Untitled
raw download clone
TEXT
views 16
,
size 1434 b
#include<stdio.h>

long long a[1000002],pos[1000002];

int BS(long long int*,long long int, int);//二分法可以找到<f的最後一格或==f的第一格

int main(void)
{
     int k,q,n,i,ans;
     long long f;
     scanf("%d%d%d",&n,&k,&q);
     for(i=1;i<=n;i++)
     {
          scanf("%lld",&a[i]);
          pos[i]=i;
          if(a[i]==a[i-1])pos[i]=pos[i-1];//位移範圍到最頭EX 2 2 5 5 5 6 變成 1 1 3 3 3 6
     }
     while(q--)
     {
          scanf("%lld",&f);
          if(f>a[n])printf("gan ni nya sai bau\n");
          else
          {
               int tmp=BS(a,f,n);//直接二分搜,再搬動位置
               if(a[tmp]<f)tmp++;
               tmp=pos[tmp];
               if(a[k+1]==a[tmp])printf("1\n");//CASE:k剛好切到重覆數字的中間
               else
               {
                    ans=tmp-k+n*((tmp-k)<=0);
                    printf("%d\n",ans);
               }
          }
     }

     return 0;
}

int BS(long long int* data,long long int q,int n)
{
     int low = 1, high = n, mid;

    while (low < high)
    {
        mid = (low + high) / 2;

        if (data[mid] == q)
        {
            return mid;
        }
        else if (data[mid] > q)
        {
            high = mid - 1;
        }
        else if (data[mid] < q)
        {
            low = mid + 1;
        }
    }

    return (low+high)/2;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.