今天难得做了做洛谷的题，而且还是两个！
P1075：已知正整数n是两个不同的质数的乘积，试求出两者中较大的那个质数。输入格式：一个正整数n。输出格式：一个正整数p，即较大的那个质数。
第一版代码：
#include<iostream> using namespace std; bool isZhi(int a) { if(a==1)return false; for(int i=2;i<a;i++) { if(a%i==0)return false; } return true; } int main() { int n; cin>>n; for(int x=n-1;x>1;x--) { if(isZhi(x)==true&&n%x==0) { cout<<x; break; } } }
很简单，判断质数的程序已经讲过很多遍了。main函数中，从n-1往下减，如果遇到一个既是质数又能整除原数的数，就输出并停止。这样能保证输出的唯一质因数是最大的。
然而，交了代码以后，分数才刚好及格，未通过的4个监测点都超时了。
怎么会超时呢？我想了想。能不能让for循环检测的少一点？
对了！为什么非得检测到1？如果检测到n的平方根再往下检测，那么即使出现了质因数，它也不是最小的了！
第二版代码：
#include<iostream> #include<cmath> using namespace std; bool isZhi(int a) { if(a==1)return false; for(int i=2;i<a;i++) { if(a%i==0)return false; } return true; } int main() { int n; cin>>n; for(int x=n-1;x>=sqrt(n);x--) { if(isZhi(x)==true&&n%x==0) { cout<<x; break; } } }
先引用cmath库以调用sqrt函数。然后按照我的思路检测，完美！
然而还是超时了。。。。。。
我又一次考虑起来。能不能让检测质数的函数精简一些？
对了！函数中的迭代器i如果超过了a/2,那么就不用再加了！直接就可以判断是质数！因为i如果大于a/2，那么a/i将小于2.
第三版代码：
#include<iostream> #include<cmath> using namespace std; bool isZhi(int a) { if(a==1)return false; for(int i=2;i<=a/2;i++) { if(a%i==0)return false; } return true; } int main() { int n; cin>>n; for(int x=n-1;x>=sqrt(n);x--) { if(isZhi(x)==true&&n%x==0) { cout<<x; break; } } }
然而，又一次超时了。。。
那就是处理器的问题了！我磕碜的i3-7100真的虚了，人家i7,i9的一大片，可是我家穷其实是我妈kou men能怪我吗！
人间不值得
P1138：题目描述
现有n个正整数，n≤10000，要求出这n个正整数中的第k个最小整数（相同大小的整数只计算一次），k≤1000，正整数均小于30000。输入格式:
第一行为n和k; 第二行开始为n个正整数的值，整数间用空格隔开。输出格式:
第k个最小整数的值；若无解，则输出“NO RESULT”。注意这里，一会真香
学了排序的我想了想，桶排序应该是最好的。因为相同大小的整数只计算一次。冒泡排序最大的缺点就是不能有相同数据，否则会出来很乱的结果正好选择排序我没学好，其他排序根本不会，于是我试了试：
第一版：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int toConst(int a) { const int A=a; return A; } int b[10001]; int main() { //桶排序 int n,k; memset(b,0,sizeof(b)); cin>>n>>k; int a[toConst(n)]; for(int i=0;i<n;i++) { cin>>a[i]; b[a[i]]++;//标号为输入数据的桶，桶号即数据，桶中的值为是否有这个数据。 } for(int i=0;i<10000;i++) { if(b[i]>0) { if(k==i+1)//第i个有数据的桶，正好是第k个时 { cout<<i; return 0; } } } cout<<"NO ANSWER"; }
桶排序的思路请参见一本通我自己也讲不明白。
然而错了！
我想了想，其实最后一个注释本来就不对。i是迭代器，它只负责找桶。应当是每找到一个桶，一个变量递增，说明找到了第某个桶。当这个变量正好为k时输出这个桶的下标(即i).不能把i直接拿过来用。
第二版：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int toConst(int a) { const int A=a; return A; } int b[10001]; int main() { //桶排序 int n,k; int p=0;//检测有数据的桶数 memset(b,0,sizeof(b)); cin>>n>>k; int a[toConst(n)]; for(int i=0;i<n;i++) { cin>>a[i]; b[a[i]]++; } for(int i=0;i<10000;i++) { if(b[i]>0) { p++;//有数据 if(k==p) { cout<<i; return 0; } } } cout<<"NO ANSWER"; }
不错不错！
然而。。。成绩和上次一样！
怎么回事？哪里都没问题啊！
我悄悄看了看原题，瞥见了"NO RESULT",有看了看我的"NO ANSWER".......
哦豁！我几乎叫了起来！我怎么犯了这种错误！
第三版：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int toConst(int a) { const int A=a; return A; } int b[10001]; int main() { //桶排序 int n,k; int p=0; memset(b,0,sizeof(b)); cin>>n>>k; int a[toConst(n)]; for(int i=0;i<n;i++) { cin>>a[i]; b[a[i]]++; } for(int i=0;i<10000;i++) { if(b[i]>0) { p++; if(k==p) { cout<<i; return 0; } } } cout<<"NO RESULT";//没什么好说的了 }
人间不值得（前后照应）
原文：https://www.cnblogs.com/jiangyuechen/p/12241683.html