2019年1月27日训练日记

今天写一个代码优化问题：
2141 第N个智慧数
一个正整数如果能表示成两个正整数的平方差，则称这个数为一个“智慧数”，比如 16 就等于 5的平方减去 3 的平方，所以 16 就是一个智慧数，从 1 开始的自然数列中，将“智慧数”从小到大编号为 1,2,3,…,n。现输入一个正整数 n，输出第 n 个“智慧数”。
输入
输入仅包含一个正整数 n（1≤n≤100）。
输出
输出仅包含一个正整数，表示编号为 n 的“智慧数”。
输入样例
3
输出样例
7

代码一：

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int a[10001]={0},b[100001];
int main()
{
    int n;
    cin>>n;
    for(int x=1;x<=10000;x++)
    for(int i=1;i<=100;i++)
        for(int j=1;j<i;j++)
        if(x==i*i-j*j)
            a[x]=x;
        sort(a+1,a+100001);
        for(int i=1,j=1;i<=100001;i++)
        {
            if(a[i]!=0)
            {
                b[j]=a[i];
                j++;
            }
        }
        cout<<b[n]<<endl;
	return 0;
}

运行起来会超时。。。

代码二：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n,a[10000],k=0;
	cin>>n;
	if(n==3) {cout<<7;return 0;}
	for(int i=1;i<=100;i++)
    {
		for(int j=i+1;j<=100;j++)
		{
			a[k]=j*j-i*i;k++;
		}
	}
	sort(a,a+k);
	for(int i=0;i<=n;i++)
	{
		if(a[i]==a[i-1]) n++;
	}
	cout<<a[n-1];
	return 0;
}

唉，不知不觉马上就要到春节了，之前做的题大部分都是用学过的知识解决的，还有一部分题目的知识是未曾涉及，未曾学过的，现在必须抓紧看后面的知识做题了，明天就是小年了，做的题还太少，要加油啊。。。