PAT 乙级 1030

不愧是25分的题考的好细致。核心思想是先从小到大排序再循环处理。首先数组不能定义 int 要定义 long long int 因为 元素*p 的结果可能会超过 int所以一开始定义元素就只能定义 long long int如果直接用两个 for 循环会运行超时只能得22分。要在双重 for 循环上加一些限制条件就不会超时了。i n - maxlength;int j i maxlength; j 不需要每次都从 i 开始。v[j] v[i] * p; 不满足这个条件就不用再往后循环了。这三个限制条件能大大减少循环次数。#includebits/stdc.h using namespace std; int main() { int n, p; cin n p; vectorlong long int v(n); for(int i 0;i n; i ) cin v[i]; sort(v.begin(), v.end()); int len 0; for(int i 0; i n - len; i ) { for(int j i len; j n v[j] v[i] * p; j ) len j - i 1; } cout len endl; return 0; }