POJ 2591 Set Definition 解题报告

一、问题描述

Description

Set S is defined as follows:
(1) 1 is in S;
(2) If x is in S, then 2x + 1 and 3x + 1 are also in S;
(3) No other element belongs to S.

Find the N-th element of set S, if we sort the elements in S by increasing order.

Input

Input will contain several test cases; each contains a single positive integer N (1 <= N <= 10000000), which has been described above.

Output

For each test case, output the corresponding element in S.

Sample Input

100

254

Sample Output

418

1461

 

二、解题思路

将这一千万个数统统计算出来按大到小存入a[]数组。因为数据量大，因此不能排序。

设两个指针p2和p3，分别表示通过2x+1和3x+1得到最小值的x的下标。开始时a[1]=1,p2=p3=1;那么下一个最小值是2*a[p2]+1与3*a[p3]+1中的小者，如果是前者，则p2++，否则p3++。重复此过程直到计算完1千万个数。

三、代码

#include<iostream>
#include <algorithm>
#include<functional>
using namespace std;
const int N=10000000;
int a[N+1];
int main()
{
    int i,p2,p3;
    int x;
    int t2,t3;
    a[1]=1;
    for(i=2,p2=1,p3=1;i<=N;++i)
    {
        t2=a[p2]*2+1;
        t3=a[p3]*3+1;
        if(t2<t3)
        {
            a[i]=t2;
            p2++;
        }
        else
        {
            if(t2>t3)
            {
                a[i]=t3;
                p3++;
            }
            else
            {
                a[i]=t2;
                p2++;
                p3++;
            }
        }
    }
    while(scanf("%d",&x)!=EOF)
    {
        printf("%d\n",a[x]);
    }
    return 0;
}