PAT 1085

题目 ： Perfect Sequence

分值 ： 25
难度 ： 中等题
思路 ： 二分查找,但是你要注意你每次查找如果查找的主键在原序列中不存在,那么cur将停在比它大的位置
       如果存在就会停在他身上.
坑点 ： 二分查找两种情况停留在的下标要清晰：1）序列中有这个值 就停在这个值下标处 2）序列没这个值
       就停在第一个比这个值大的值下标处.
       然后要用 long存数据！！！

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
using namespace std;
long data[100001];
bool cmp(int a, int b)
{
    return a < b ;
}
int main() {
    int N , p ;
    cin >> N >> p ;
    for(int i = 0 ; i< N ; i++)
        scanf("%ld",&data[i]);
    sort(data,data+N ,cmp);
    int max = 1 ;
    long cur ;
    for(int i = 0 ; i< N  ; i++)
    {
        cur = data[i] * p;
        if(data[N-1] <= cur)
        {
            if(max <N-i)
                max = N - i;
            break ;
        }
        int low=i+1 , high =N ,mid ;
        while(low < high)
        {
            mid = (low+high)/2 ;
            if(data[mid] < cur)
                low = mid+1;
            else if(data[mid] >cur)
                high = mid ;
            else if(data[mid]==cur)
            {
                high = mid+1 ;
                break ;
            }
        }
        if( high - i > max)
            max = high - i ;
    }
    cout << max <<endl ;
}