链家2018春招C++工程师编程题题解

第一题：

set处理一下，输出set的容量就行

#include <bits/stdc++.h>

using namespace std;

int main()
{
    for (int n; cin >> n; ) {
        set<int> st;
        for (int i = 0, k; i < n; i++) {
            cin >> k;
            for (int j = 0, x; j < k; j++)
                cin >> x, st.insert(x);
        }
        cout << st.size() << endl;
    }
    return 0;
}

第二题：

转换下思路，如何保留更多的木条，1 2 3 5 8 ...这些木棍可以保留下来，那么这个问题就解决了。

#include <bits/stdc++.h>

using namespace std;

#define TOP 100000

int main()
{
    vector<int> dp(3);
    dp[1] = 1, dp[2] = 2;
    for (int i = 3; dp[i - 1] + dp[i - 2] <= TOP; i++)
        dp.push_back(dp[i - 1] + dp[i - 2]);
    for (int n; cin >> n; ) {
        auto it = lower_bound(dp.begin(), dp.end(), n);
        cout << *it - (it - dp.begin()) - (*it == n ? 0 : *it - n - 1)<< endl;
    }
    return 0;
}