먼 친척 보다 가 까 운 이웃 이 낫다.

제목 링크
시간 제한: C / C + + 3 초, 기타 언어 6 초 공간 제한: C / C + + 256 M, 기타 언어 512 M 열도 지수: 1372
제목 설명
소 와 소 는 최근 에 새로운 도시 로 이사 했다. 이 도 시 는 1 차원 좌표계 로 볼 수 있다.도시 에는 n 명의 주민 이 있 고, i 번 째 주민 의 위 치 는 aiai​。현재 소 와 소 는 m 개의 이사 방안 이 있 는데, i 번 째 방안 에서 그 는 위치 로 옮 길 것 이다 xixi​。  
속담 에 이 르 기 를, 먼 친척 은 가 까 운 이웃 보다 못 하 다 고 한다.현재 소 는 이사 방안 마다 이사 후 가장 가 까 운 주민 과 의 거리 가 얼마나 되 는 지 알 고 싶 어 한다.
 
예시 1
입력

3,2,[2,4,7],[5,8]

출력

[1,1]

설명 하 다.
첫 번 째 방안 은 5 로 옮 겨 5 가장 가 까 운 주민 과 위치 4, 거 리 는 1 이다.
두 번 째 방안 은 위치 8 로 옮 겨 8 가장 가 까 운 주민 과 위치 7, 거 리 는 1 이다.
비고:
1\le n,m\le100000, 0\le |a_i|,|x_i|\le 1e91≤n,m≤100000,0≤∣ai​∣,∣xi​∣≤1e9
첫 번 째 매개 변 수 는 int 형 변수 로 주민 개수 n 을 대표 합 니 다.
두 번 째 매개 변 수 는 int 형 변수 로 방안 의 개수 m 를 대표 합 니 다.
세 번 째 매개 변 수 는 vector 이 고 n 개의 요 소 를 포함 하여 n 개의 주민 의 위 치 를 대표 합 니 다.
네 번 째 매개 변 수 는 vector 이 고 m 개의 요 소 를 포함 하여 m 개의 방안 에 대응 하 는 위 치 를 대표 합 니 다.
2 점 찾기 연습

#include

class Solution {
public:
    /**
     *       
     * @param n int       
     * @param m int       
     * @param a int  vector      
     * @param x int  vector        
     * @return int  vector
     */
    //     
    //int FindPosition(vector& a,int key);
    //        
    int FindPosition(vector& a,int key)
    {
        int nStar = 0;
        int nEnd = a.size() - 1;
        int nCur = (nStar + nEnd) / 2;
        
        //         int      
        // int nSmallestPos = 2^31 - 1 + 2^31;
        int nSmallestPos  = 2147483647;
        
//)        while(nStar != nEnd)
        while(nStar <= nEnd )
        {
            //          
            if(a[nCur] == key)
                return 0;
            
            //                 
            if(a[nCur] < key)
            {
                //       
                if(key - a[nCur] < nSmallestPos)
                {
                    nSmallestPos = key - a[nCur];
                }
                
                //       
                nStar = nCur + 1;
            }
            
            //                 
            if(a[nCur] > key)
            {
                //       
                if(a[nCur] - key < nSmallestPos)
                {
                    nSmallestPos = a[nCur] - key;
                }
                
                //        
                nEnd = nCur - 1;
            }
            
            //      ,       ，   
            nCur = (nStar + nEnd) / 2;
        }
        return nSmallestPos;
    }
    
    vector solve(int n, int m, vector& a, vector& x) {
        // write code here
        
        vector obj;
        
        //   a            
        //  a      
        sort(a.begin(), a.end());
        
        for(unsigned int i = 0; i < x.size(); i++)
        {
            //   2         。
            obj.push_back(FindPosition(a, x[i]));
        }

        return obj;
    }
};