PAT 1085（patty）
1、题目链接
https://patest.cn/contests/pat-a-practise/1085
2、题目分析
（1）题意：给出一串数字，然后给出一个数p，请从这串数字中找出可以存在的数字序列，序列中的最大值max与最小值满足max<=min*p；使得这样的序列包含的数字尽量最大
（2）分析：我们可以使用two pointers的方法来实现着一题。
3、问题
（1）在一次次的排除可以排除完的bug之后，我们会发现，有一个难以接受的问题。“时间限制”，对，我们可以看到如果使用下述的代码其余的测试点都会通过，但是会有一个时间超过的问题。代码如下:
#include
#include
using namespace std;
#define size 100002
/*
1.使用two pointer
*/
int main(){
long long n,p;
scanf("%ld %ld",&n,&p);
int i ;
long long array[size];
for(i = 0;i= i){
if(number > (j - i +1)){//如果说number的值已经大于两者的距离，则不再比较
break;
}
else{
if(array[j] <= array[i] * p){//如果满足条件
if(number <(j - i + 1)){
number = j - i + 1;
}
break;//只要满足这个情况，就break掉
}
else{
j--;
}
}
}
}
printf("%d",number);
}
/*测试点
10 8
2 3 20 4 5 1 6 7 8 9
10 8
2 3 25 4 5 10 6 7 8 9
2 5
6 40
*/这里给出了几个测试点，可以供大家测试
（2）我们想想一下，我们这里先是对一串数字进行排序，即使用sort(array,array+n),然后从这个数组中找出满足题意的最长子序列。即如下代码实现的功能：
for(i = 0 ; i < n ; i++){
int j = n - 1;
while(j >= i){
if(number > (j - i +1)){//如果说number的值已经大于两者的距离，则不再比较
break;
}
else{
if(array[j] <= array[i] * p){//如果满足条件
if(number <(j - i + 1)){
number = j - i + 1;
}
break;//只要满足这个情况，就break掉
}
else{
j--;
}
}
}
} 但是，我们是否注意到，如果对于一个已经选择好的数字array[i]，我们已经知道了它的最长子序列为number个。如果我们对array[i+1]中的j再从i开始， 则处理速度太慢。即会超时，所以我们从刚才那个处理array[i]的j值开始就可以。这样就会避免时间超时的问题。正确代码如下：
#include
#include
using namespace std;
#define size 100002
/*
1.使用two pointer
*/
int main(){
long long n,p;
scanf("%ld %ld",&n,&p);
int i ;
long long array[size];
for(i = 0;i array[i] * p){
break;//如果是这种情况则跳出循环
}
j++;
}
}
printf("%d",number);
}
/*测试点
10 8
2 3 20 4 5 1 6 7 8 9
10 8
2 3 25 4 5 10 6 7 8 9
2 5
6 40
*/
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
暂时没有评论，来抢沙发吧~