PAT A1085 TwoPointers解法

快来打我* 2022-02-22 11:58 123阅读 0赞

**一、题目:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]  
**二、代码：**

#include<cstdio>
    #include<algorithm>
    using namespace std;
    
    #define N_max 100001
    int num[N_max];
    
    int main() {
        int N, p;
        scanf("%d %d", &N, &p);
        for(int i = 0; i < N; i++) {
            scanf("%d", &num[i]);
        }
        sort(num, num + N);
        int head = 0, tail = 0, count_num = 0;
        while(tail < N) {
            while(tail < N && num[tail] <= (long long)num[head] * p) tail++;
            count_num = max(tail - head, count_num);
            head++;
        }
        printf("%d", count_num);
        return 0;
    }

**三、问题与解决：**  
采用TwoPointers思想，但是测试点4无法通过(现已解决)；  
错误写法：

long long result;
    result = num[head] * p;

由于测试点4的数据会超出int能表示的数据范围，所以num\[head\] \* p 的结果是负数，而上述代码的写法会被理解为把这个负数存储在result中，而实际上需要的是把乘积按照long long来理解。

正确写法：

（long long）num[head] * p

详见代码。

**四、总结**  
数据溢出问题，是比较隐蔽的问题， 下次遇到需谨慎。

PS：希望给有同样问题的小伙伴带来帮助。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70]: /images/20220222/eeec7a3763c04b458d510f0b7da92f07.png

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python实现Pat 1085. Perfect Sequence (25)

[题目][Link 1] Given a sequence of positive integers and another positive integer p. Th

左手的ㄟ右手/ 2022年06月04日 06:53/ 0 赞/ 105 阅读

相关 1085. PAT单位排行 (25)

每次 PAT 考试结束后，考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。输入格式：输入第一行给出一个正整数N（<=105），即考生人数。随后N行，每行按下

末蓝、/ 2022年05月26日 10:00/ 0 赞/ 102 阅读

相关 PAT1085:Perfect Sequence

1085 Perfect Sequence （25 分） Given a sequence of positive integers and another positive

红太狼/ 2022年05月10日 14:28/ 0 赞/ 123 阅读

相关 PAT A1063

![clipboard.png][] 这里面还是用到了set去重，还是要多掌握stl的用法；这里注意一个巧妙地处理；由于我们寻找的时两个集合a,b的不重复元素，

以你之姓@/ 2022年03月07日 14:22/ 0 赞/ 131 阅读

相关 PAT A1121

![clipboard.png][] 水题，但是通过这一题需要改进一点；对于hash赋初值的时候一定要谨慎一点，不要随便赋值0，视输入的数据而定； inclu

今天药忘吃喽~/ 2022年03月07日 10:44/ 0 赞/ 153 阅读

相关 PAT A1029

![clipboard.png][] 起先自己想尝试性的直接排序找中位数，内存直接超限；其实这道题可以采用归并排序的思路来做：但是示例依旧白给。。。不过还是展现了

﹏ヽ暗。殇╰゛Y/ 2022年03月07日 10:24/ 0 赞/ 168 阅读

相关 PAT A1043

![clipboard.png][] 简单的不用考虑平衡的二叉查询树；我发现我有读题障碍症。。。 include<iostream> include

迷南。/ 2022年03月07日 03:46/ 0 赞/ 158 阅读

相关 PAT A1085 TwoPointers解法

一、题目: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

快来打我*/ 2022年02月22日 11:58/ 0 赞/ 124 阅读

相关 PAT A1029 TwoPointers解法

一、题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

拼搏现实的明天。/ 2022年02月21日 01:47/ 0 赞/ 153 阅读

相关 PAT A 1025 PAT Ranking

1025 PAT Ranking (25 分) Programming Ability Test (PAT) is

怼烎@/ 2022年02月01日 10:53/ 0 赞/ 161 阅读