一道C/C++程序题

题目:当M为0时,A[0]=0;当M大于0时,A[M]=A[M-1]-M.若这个A[M]小于等于0或者其值已经出现在A数组中,则用另外一公式A[M]=A[M-1]+1.求输入一个数K,输出A[K]的值.数组值为0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 ...K值最大为50万

原题是英文的:The Recaman's sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−1 + m. (m是下标)
The first few numbers in the Recaman's Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 ...
Given k, your task is to calculate ak.

#include<iostream>
using namespace std;
int a[500001];
int main()
{
int i,j,n;
while(n!=-1)
{
cin>>n;

for(i=0;i<=n;i++)
{
if(i==0)a[i]=0;
if(i!=0)
{
a[i]=a[i-1]-i;
if(a[i]<=0)a[i]=a[i-1]+i;
for(j=0;j<i;j++)

 
 
 
你的程序的确是如 xniren 所说，线性搜索消耗的时间太多。
你用的是 C++，大可利用标准库里的 set 类。
set 是用平衡二叉树实现的，所以它的添加、移除和搜索都是 O(log n) 操作，快得多：

#include <set>
#include <iostream>
using namespace std ;

int a[ 500001 ],
    m = 1;
set<int> existing;

int main( ) {
    for ( int k; cin >> k && k != -1; ) {
        for ( ; m <= k; m++ ) {
            int current = a[ m - 1 ] - m;
            if ( current <= 0 || ! existing.insert( current ).second )
                existing.insert( current += 2 * m );
            a[ m ] = current;