1030. 完美數(shù)列(25)

時間限制 300 ms
內(nèi)存限制 65536 kB
代碼長度限制 8000 B
判題程序 Standard 作者 CAO, Peng

給定一個正整數(shù)數(shù)列，和正整數(shù)p，設(shè)這個數(shù)列中的最大值是M，最小值是m，如果M <= m * p，則稱這個數(shù)列是完美數(shù)列。

現(xiàn)在給定參數(shù)p和一些正整數(shù)，請你從中選擇盡可能多的數(shù)構(gòu)成一個完美數(shù)列。

輸入格式：

輸入第一行給出兩個正整數(shù)N和p，其中N（<= 10⁵）是輸入的正整數(shù)的個數(shù)，p（<= 10⁹）是給定的參數(shù)。第二行給出N個正整數(shù)，每個數(shù)不超過10⁹。

輸出格式：

在一行中輸出最多可以選擇多少個數(shù)可以用它們組成一個完美數(shù)列。

輸入樣例： 10 8 2 3 20 4 5 1 6 7 8 9 輸出樣例： 8 解析:這道題是PAT乙里面比較難的一題,里面涉及到優(yōu)化設(shè)計,這道題也是最優(yōu)題目中的一個代表. 代碼如下:
/*************************************************************************> File Name: 1030.c> Author: YueBo> Mail: yuebowhu@163.com> Created Time: Fri 02 Jun 2017 09:19:45 PM CST************************************************************************/#include <stdio.h> #include <stdlib.h>int cmp(const void *a, const void *b) {return *(double *)a - *(double *)b; }int main() {int N, i, j;double p;int cnt, max = 0;scanf("%d%lf", &N, &p);double *arrs = (double *)malloc(N*sizeof(double));for (i = 0; i < N; i++)scanf("%lf", arrs+i);qsort(arrs, N, sizeof(double), cmp);for (i = 0; i < N; i++){cnt = 0;for (j = max+i; j < N; j++){if (arrs[j]/arrs[i] <= p)cnt++;elsebreak;}if (cnt > 0)max = cnt + max;}printf("%d\n", max);return 0; }

總結(jié)

以上是生活随笔為你收集整理的1030. 完美数列(25)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。