首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1030 完美数列 (25 分)

1030 完美数列 (25 分)

作者头像
可爱见见
发布2019-09-09 15:56:45
3800
发布2019-09-09 15:56:45
举报
文章被收录于专栏:卡尼慕卡尼慕

1030 完美数列 (25 分)

给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 Mmp,则称这个数列是完美数列。

现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。

输入格式:

输入第一行给出两个正整数 Np,其中 N(≤105)是输入的正整数的个数,p(≤109)是给定的参数。第二行给出 N 个正整数,每个数不超过 109。

输出格式:

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例:

10 8
2 3 20 4 5 1 6 7 8 9

输出样例:

8

我的代码

// 1030 完美数列 (25 分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

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

bool cmp(int a, int b) {
    return a < b;
}

int main() {
    //输入
    int input, p;
    cin >> input >> p;
    vector<double> input_total;
    double tmp;
    for (int i = 0; i < input; i++) {
        cin >> tmp;
        input_total.push_back(tmp);
    }
    //排序
    sort(input_total.begin(), input_total.end(), cmp);
    //从最大值开始往前循环
    int max_index = input_total.size() - 1;
    int res = 0, cnt = 0;
    int j;
    for (int i = 0; i < input_total.size(); i++) {
        //把当前i作为最小值
        tmp = input_total[i] * p;
        for (j = cnt; j < input_total.size(); j++) {
            if (input_total[j] > tmp)
                break;
            if (j - i >= res)
                res = j - i + 1;
        }
        cnt = j;
    }
    cout << res;
}

思路

首先要对输入进行排序,然后从最小值开始,每个最小值找到对应的最大值,看看vector中是否存在满足最大值的数。若存在,则获取最大值索引,比较res,若大于res则更新res,若小于res,就下一次遍历即可。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-09-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 卡尼慕 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 输入格式:
  • 输出格式:
  • 输入样例:
  • 输出样例:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档