大家好，又见面了，我是你们的朋友全栈君。
上周末去隔壁大学参加了PAT乙级的考试，结果没想到第一次考试就出了点小问题…
本来考试是在1.30全国各个考点都同时开始（因为要排名），结果快到1.30的时候机房连不上网络，最后我们这个考点直接移后到将近2.30才开始考试，虽然结束时间也移后了，不过这多年不遇的突发情况直接让我遇到也太真实了。。。
小插曲过后，再说下考试内容，乙级确实难度不大，三小时五道题，前两道题基本是送分题，虽然作者本人比较菜花了四五十分钟，但基本也在可接受范围内。
接下来主要说下这个第三题，这题真的坑我不浅，简单说下题目：输入两个数n，m（0<=n<m<=25000)，在此范围内找到一个数a使得它与另外一个（0，25000）范围得数b满足如下关系:a^3 – (a-1)^3=( b^2+ (b-1)^2) ^2(原题不是这样给的，这是换算完的结果），然后满足此关系的数对a,b按照a的大小顺序输出在屏幕上，如果找不到则输出No Solution
简单分析下这题，显然暴力使用双重循环遍历一定会超时，所以在外层循环确定了a时，内层查找b时使用二分的办法就不会超时了。
我当时的第一思路就是如此，但是在写第二层的二分查找时，出现了一个问题：对于给定的m，n只能找出一组答案，第二次进入循环时，L和R（左右端点）的值不会改变，所以导致只能找到一组解。当时百思不得其解，花了一个多小时在上面也没能成功找出问题。考试结束后我根据回忆重新写了这道题（基本与我考试写的一模一样），试图找出问题所在，结果程序运行结果竟然正确。。。下贴出代码：（考试和我本机都是使用DEVC++，只不过考试时的版本稍老一些）
//0<n<m<25000,(a^3-(a-1)^3)=(b^2+(b-1)^2)^2
#include <iostream>
using namespace std;
long long a3(long long a)
{
return (a*a*a-(a-1)*(a-1)*(a-1));
}
long long b2(long long b)
{
return (b*b+(b-1)*(b-1))*(b*b+(b-1)*(b-1));
}
int main()
{
int n,m;
long long l=1,r=25000;
long long mid;
cin >> n >> m;
for(int i=n;i<=m;i++)
{
l=1;
r=25000;
while(l<=r)
{
mid=(r-l)/2+l;
if(a3(i)==b2(mid))
{
cout << i << ' ' << mid << endl;
break;
}
else if(a3(i)>b2(mid))
{
l=mid+1;
}
else
{
r=mid-1;
}
}
}
return 0;
}
真的很怪。。因为我坚信我的思路没错，在那里debug一个多小时，导致后面的题（第四题和这道题差不多，第五题涉及到链表，稍微麻烦一些）没什么时间做。。难顶
不过上述代码确实也不是完美的，有什么缺陷希望有大佬可以指教一下，也许能启发我想到考试中我到底这道题出了什么问题
总体来说乙级不是很难，基本不涉及什么算法和数据结构，虽然出了点小插曲不过拿来练手还是不错的，明年甲级倒是要好好考一下
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/132537.html原文链接：https://javaforall.net
