个人练习-PAT甲级-1085 Perfect Sequence

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805381845336064

刚开始以为形成的新子数列是要顺序和原数列一致的，感觉要用dp，有点难啊。。然而这题25分，查了一下果然原数列只是提供这些数字，没有顺序之类的要求，那就简单了。

一个注意点是虽然每个给出的数据都不超过int的范围，但相乘了可能就超过范围，所以让p为long long int这样计算m*p时可以自动把结果转换为long long int

先从小到大排序，开始遍历，让m为arr[i]，然后从i+len开始找M。len为最终结果【因为长度要更大才会更新，小的长度没必要考虑，节省时间】
如果到了某个点无法满足M<=m*p了，及时break，不然会超时。

    sort(arr.begin(), arr.end());for (int i = 0; i < N; i++){
    int tmp_len;for (int j = i + len; j < N; j++){
    if (arr[j] <= p*arr[i]){
    tmp_len = j - i + 1;if (tmp_len > len)len = tmp_len;}elsebreak;}}

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;int main() {
    int N, len = 1;long long int p;scanf("%d %lld", &N, &p);vector<int> arr(N);for (int i = 0; i < N; i++)scanf("%d", &arr[i]);sort(arr.begin(), arr.end());for (int i = 0; i < N; i++){
    int tmp_len;for (int j = i + len; j < N; j++){
    if (arr[j] <= p*arr[i]){
    tmp_len = j - i + 1;if (tmp_len > len)len = tmp_len;}elsebreak;}}printf("%d", len);return 0;
}