몇 개의 집을 훔칠 수 있습니까?

Question

최근에 소프트웨어 위치에 대한 인터뷰에서 다음 질문을 받았습니다. 내가 기억할 수있는 한 그것은 다음과 같다 : 배열 A [1 ... n]이 정렬 된 순서로 각각의 위치를 ​​포함하는 스트레치에있는 n 집이있다.

예를 들어, 배열 A[] = {1,3,5,10}을 고려하십시오. 각 집에는 하나의 금화가 있습니다. 도둑이되어서도 k 집에서 금화를 훔치려 고합니다.

하지만 제한이 있습니다 : k 개의 집을 선택한 경우 선택한 두 집 사이의 거리 차이는 k 이상이어야합니다. 위의 예에서 : k = 3 인 경우 위치가 1,5,10 인 집을 선택할 수 있습니다. k = 4 인 경우 위의 제약 조건을 기반으로 4 개 주택을 선택할 수 없습니다.

최대로 만들고 싶습니다.입니다.

위의 예에서 k = 3이 예상되는 대답입니다.

현재 나는 무수한 순진한 알고리즘을 가지고 있습니다. 1에서 시작하는 모든 k 값에 대해 집 선택이 가능한지 확인합니다. 가능하면 k을 증분하고 동일한 작업을 다시 수행하십시오.

더 효율적으로 해결할 수 있습니까?

Answer 1

아이디어 : 이진 검색 k 값.

다음, 1st 집을 선택 옆에 집을 선택 유지 :

는 배열 mid의 주어진 값이 유효한 대답 경우 그냥 욕심 전략을 사용, 확인하려면 지금

low=1 
high=min(n,sqrt(a[n] - a[1])) 
while(low<=high) 
    mid = (low+high)/2 
    if(mid is a valid answer) 
     low=mid+1 
    else 
     high=mid-1 

return high 

를 정렬하자 마지막으로 선택한 집으로부터 적어도 mid 떨어진 거리이고, 집의 강도가 mid 이상이면 그렇지 않으면 유효한 도용이 가능합니다.

복잡성 : O