首页 > 代码库 > PAT 1085. Perfect Sequence

PAT 1085. Perfect Sequence

还好只是要求长度,如果是完整序列的话估计得跪

#include <cstdio>#include <climits>#include <cstdlib>#include <algorithm>using namespace std;int main() {    int N,p;    scanf("%d%d", &N, &p);    if (N < 1) {        printf("%d\n", 0);        return 0;    }    vector<int> seq(N);        for (int i=0; i<N; i++) {        scanf("%d", &seq[i]);    }        if (N < 2) {        printf("%d\n", 1);        return 0;    }        sort(seq.begin(), seq.end());        long long m = seq[0];    long long M = seq[0];        int i = 0, j = 1;    int max_len = 1;    int cur_len = 1;    while (i < j && j < N) {        m = seq[i];        M = seq[j];                if (M <= m * p) {            cur_len = j - i + 1;            j++;        } else {            while (M > m * p) {                m = seq[++i];            }        }                if (cur_len > max_len) {            max_len = cur_len;        }    }        printf("%d\n", max_len);    return 0;}

 

PAT 1085. Perfect Sequence