1571. 完美序列

WA 代码

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, p;

int main(){
    scanf("%d%d", &n, &p);
    int a[N];
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    //max <= min * p
    int max = 0, min = 0, M = 0, res = 0;
    for(int l = 0, r = 1; r < n; r ++ ){
        min = a[l];
        max = a[r];

        if (max <= min * p){
            M = r - l + 1;
            if (M > res)    res = M;
        }
        else{
            l ++ ;
        }
    }
    printf("%d", res);
    return 0;
}

其实这段代码只要把 r 改为 0，并把声明 min 为 long 型（或强制类型转换），也能 AC。

为什么？？？

min * p 可能会溢出，所以 long min，这个好理解。

为什么要把 r 改为 0？
因为会过不了样例：

1 8
2

序列总共就一个数······

AC 代码

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, p;

int main(){
    scanf("%d%d", &n, &p);
    int a[N];
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    //max <= min * p
    int res = 0;
    for(int l = 0, r = 0; r < n; r ++ ){
        while(l < r && a[r] > long(a[l]) * p)   l ++ ; // 当不满足条件时，移动左指针
        res = max(res, r - l + 1);
    }
    printf("%d", res);
    return 0;
}

AC 代码除了我上面说的两点外其实也没别的······