AcWing 1571. 完美序列---双指针

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1571. 完美序列---双指针原题链接简单

作者：

巨鹿噜噜噜路 , 2020-06-10 09:42:31 , 所有人可见 , 阅读 1852

13

3

$i$指向最大的数
$j$指向最小的数
如果不符合$M≤m×p$ 则向右移动$j$指针，直至符合条件为止

C++ 代码

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;
int n;
long long arr[MAX_N], p;

int main() {
    cin >> n >> p;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    int cnt = 0;
    for(int i = 0, j = 0; i < n; i++) {
        while(j < n &&  arr[i] > arr[j] * p) j++;
        cnt = max(cnt, i - j + 1);
    }
    printf("%d", cnt);
    return 0; 
}

8 评论

NEW_FIGHT 5个月前

如果以i为左端点，j为右端点为什么会超时

zq_5 7个月前

跟大佬思路一模一样，就是没开long long一直不AC

Lukesu 2022-09-27 11:23

大佬，请问为什么我这段代码不能AC呢？

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

int N, res, num, p, max_res = 0;
int v[123456];

signed main(){
    cin >> N >> p；
    for(int i = 0; i < N; i++){
        cin >> v[i];
    }
    sort(v, v + N);

    res = N;   //res初始化为最大区间值

    //1、从前往后找可能的最长区间
    for(int i = 0, j = N - 1; i < j; j--){
        if(p * v[i] >= v[j]) break; //满足条件就跳出
        --res;  //不满足条件res减1，最右边的指针往左一步
    }
    max_res = res;

    //2、从后往前找可能的最长区间
    res = N;
    for(int i = 0, j = N - 1; i < j; i++){
        if(p * v[i] >= v[j]) break;  
        --res;
    }

    max_res = max(max_res, res); //取两次区间的最大值
    cout << max_res << "\n";

    return 0;
}