louisfghbvc的部落格

思路:

很簡單的題目(?，公式題目給你了，那就照做吧。T(n) 則要注意，i可以先從1然後檢查是否存在於S中，如果存在於S中在+1，再檢查，直到不在S中。檢查可以2分搜，因為這數列一定是小到大排序過。但這題O(n)搜尋也可過。

代碼:

#include <iostream>
using namespace std;
bool find_num(int arr[], int x, int size){
    for(int i = 1; i <= size; ++i){
        if(arr[i] == x)
            return true;
    }
    return false;
}
int main()
{
    int n;
    while(cin >> n){
        int s[n + 2], t[n + 2];
        s[1] = 1, t[1] = 2;
        for(int i = 2; i <= n; ++i){
            s[i] = s[i - 1] + t[i - 1];
            t[i] = t[i - 1] + 1;
            while(find_num(s, t[i], i)){
                t[i]++;
            }
        }
        cout << s[n] << "\n";
    }
    return 0;
}