PAT (Basic Level) Practice （中文）1030 完美数列 (25 分)

题目：

1030 完美数列 (25 分)

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

现在给定参数 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

题目分析：

求最大最小值间元素的最大个数。

策略：先排序，再用滑动窗口法求最大个数。

坑点：

1. 数据类型应为long long，最大值为最小值乘p，而最小值与p都可达到10^9，相乘有10^18，超出了int的范围。如果用int，最后一个测试点答案错误。
2. 排序用快排等高效排序，排序效率不高，倒数第二个测试点超时。

代码：

#include<stdio.h>

void Read(long long Array[], int n);//读取数组
int Solve(long long Array[], int n, int p);//滑动窗口找最大元素个数
void Sort(long long Array[], int start, int end);//快排
void swap(long long Array[], int i, int k);//数组指定元素交换，辅助快排

int main()
{
    int n, p;
    scanf("%d %d", &n, &p);
    long long Array[n];

    Read(Array, n);//读取数组
    Sort(Array, 0, n);//排序
    int ans = Solve(Array, n, p);//找最大元素个数

    printf("%d", ans);
    return 0;
}

void swap(long long Array[], int i, int k)
{
    if(i!=k)
    {
        Array[i] ^= Array[k] ^= Array[i] ^= Array[k];
    }
}

void Sort(long long Array[], int start, int end)
{
    if(start<end)
    {
        int key = Array[start];//以第一个元素为中枢
        int i = start, k;
        for(k = i+1;k<end;k++)//先将小于中枢的元素置于数组前端
        {
            if(key>Array[k])
            {
                swap(Array, k, ++i);
            }
        }
        //将中枢归位
        Array[start] = Array[i];
        Array[i] = key;

        //排序剩余部分
        Sort(Array,start,i);
        Sort(Array,i+1,end);
    }
}

int Solve(long long Array[], int n, int p)
{
    int s, e, ans = 0;
    s = e = 0;
    while(s<n)
    {
        if(Array[e]<=Array[s]*p&&e<n)//如果此时的最大值符合条件，窗口右边界右移，窗口扩大
            e++;
        else
        {
            if(e-s > ans) ans = e-s;//更新最大元素个数
            s++;//窗口左边界右移，窗口缩小
        }
    }
    return ans;
}

void Read(long long Array[], int n)
{
    int i;
    for(i=0;i<n;i++)
        scanf("%lld", &Array[i]);
}