【PAT乙级】1030 完美数列 (25 分) 二分查找做法

测试用例规模为1e5，而时间限制是200ms,说明这题肯定会卡时间
朴素的做法是先对数组排序,再二重循环
先枚举最小值出现的下标，再枚举最大值出现的下标一一比对
这样做的时间复杂度是O（n^2），肯定会超时
因此只要再第二层枚举的时候将顺序查找改成二分查找，时间复杂度降至O（n^logn）
代码如下

#include
using namespace std;
typedef long long LL;
const int N = 1e5+10;
LL a[N];
LL b[N];
int n,p;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>p;
    for(int i = 0;i>a[i];
    sort(a,a+n);
    for(int i = 0;i>1;
            if(a[mid]<=p) {
                left = mid+1;
                ans = max(ans,mid-i+1);
            } else {
                right = mid-1;
            }
        }
    }
    cout< 
PS: 
① C++STL自带二分查找函数，如果是考试就直接调STL，不用手写二分了
 ② 其他博客的做法很多都是把第二层循环的起始下标改成j+ans，没用二分查找
 这样的时间复杂度依然是O(n^2) 能AC明显是因为这题数据太弱
 我用二分19ms，而二重循环18ms，只能说明这题测试数据比较特殊
 ③ PAT1060爱丁顿数，和这题基本一样
 
注意 
数据需要用 long long 储存
 记得测试数组长度为1的情况
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713729.html