A1085

1085 Perfect Sequence (25 分)

Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification: Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤10 ​5 ​​ ) is the number of integers in the sequence, and p (≤10 ​9 ​​ ) is the parameter. In the second line there are N positive integers, each is no greater than 10 ​9 ​​ .

Output Specification: For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input: 10 8 2 3 20 4 5 1 6 7 8 9 Sample Output: 8

分析

给一个序列和一个参数p，要求找到一个被叫做完美序列的子序列sque，其中sque中的最小值与p的乘积要大于等于sque中的最大值

法1

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

int n;
long long m;    //由于m*sque[i]可能会超过int，所以将m设为long long型
int maxLength = 0;  //完美序列的最大长度

int main()
{
    scanf("%d%lld", &n, &m);
    vector<int> sque(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &sque[i]);
    }
    sort(sque.begin(), sque.end());
    for (int i = 0; i < n; i++) //从序列小的开始，找到以sque[i]为最小值的最长完美序列
    {
        //因为sque[i]的最长完美序列为maxLength，其尾元素就是sque[i+maxLength]
        //那么sque[i+1]的最长完美序列的尾元素必定大于等于sque[i+maxLength],所以直接在i+maxLength处开始找即可
        for (int j = i + maxLength; j < n;j++)  
        {
            if(sque[i]*m>=sque[j])
            {
                int tempLength = j - i + 1;
                if(tempLength>maxLength)
                    maxLength = tempLength;
            }
            else    //找到最大尾元素了即终止本次查找
                break;  //此句不加测试点4超时
        }
    }
    printf("%d", maxLength);
}

法2

使用upper_bound()函数

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

int n, maxLength = 0;
long long m;

int main()
{
    scanf("%d%lld", &n, &m);
    vector<int> sque(n);
    for (int i = 0; i < n;i++)
    {
        scanf("%d", &sque[i]);
    }
    sort(sque.begin(), sque.end());
    for (int i = 0; i < n;i++)
    {
        int tempLength = upper_bound(sque.begin(), sque.end(), sque[i] * m) - sque.begin() - i;
        if(tempLength>maxLength)
            maxLength = tempLength;
    }
    printf("%d", maxLength);
    return 0;
}

---

本文章使用limfx的vscode插件快速发布