专栏首页刷题笔记1030 完美数列 (25 分)

1030 完美数列 (25 分)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/shiliang97/article/details/100092292

1030 完美数列 (25 分)

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

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

输入格式:

输入第一行给出两个正整数 N 和 p,其中 N(≤10​5​​)是输入的正整数的个数,p(≤10​9​​)是给定的参数。第二行给出 N 个正整数,每个数不超过 10​9​​。

输出格式:

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

输入样例:

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

输出样例:

8

看了柳婼的思路才恍然大雾

可以遍历,但一定会超时,所以整一个max,进行撑杆跳就行了

思路:

1.存进去,然后sort从小到大排列,从头一个一个尝试,能有几个满足条件。

2.肯定会超时,所以设置一个max 存储最大的个数,内层循环每次都直接跳到 i+max看是否符合条件,这样就不会超时了

3.int精度不够,最后一个测试点过不去,换成long long int过了、

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	long long int  n,p;
	cin>>n>>p;
	vector<long long int> num(n);
	for(int i=0;i<n;i++)cin>>num[i];
    sort(num.begin(),num.end());
	int max=0;
	for(int i=0;i<n;i++)for(int a=i+max;a<n&&num[a]<=num[i]*p;a++)max++;
	cout<<max;
	return 0;
}

惯例比较柳婼的代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    long long p;
    scanf("%d%lld", &n, &p);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    int result = 0, temp = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + result; j < n; j++) {
            if (v[j] <= v[i] * p) {
                temp = j - i + 1;
                if (temp > result)
                    result = temp;
            } else {
                break;
            }
        }
    }
    cout << result;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode第 160 场周赛】5239. 循环码排列

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 【2020HBU天梯赛训练】7-51 分而治之

    分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。...

    韩旭051
  • cf1043F. Make It One(dp 容斥原理)

    首先,如果答案存在,那么最多为\(7\)(因为前\(7\)个质数乘起来\(>= 3e5\))

    attack
  • 最大子段和问题

    问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

    我没有三颗心脏
  • flower

          题目链接:http://acm.zzuli.edu.cn/problem.php?id=2261

    Ch_Zaqdt
  • LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

    ShenduCC
  • Codeforces Round #546 (Div. 2) C. Nastya Is Transposing Matrices(思维)

    题目链接:https://codeforces.com/contest/1136/problem/C

    Ch_Zaqdt
  • 旋转不变的感知哈希

    package com.imageretrieval.features; import com.imageretrieval.utils.ImageUtil;...

    Venyo
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633

扫码关注云+社区

领取腾讯云代金券