2017滴滴春招笔试

感觉智力题错了几个。。
编程题两题 第一题字符串翻转。。这么弱智就不说了
第二题俄罗斯套娃
有n个套娃 并给出他们的长和宽，能够套住的条件是大的套娃的长宽都大于小套娃。
首先按长排个序，如果长一样。宽降序排列。这样我们处理的时候可以保证长是逐渐递增，只要判断宽
代码如下

#include<bits/stdc++.h>

using namespace std;

    bool compare(const pair<int, int> &a, const pair<int, int> &b)
    {
        if (a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    }

pair<int, int> a[55];
int dp[55];

int main()
{
    int n;
    cin >> n;
    for (int i=0; i < n; i++)
    {
        int a1,a2;
        cin >> a1 >> a2;
        a[i] = make_pair(a1, a2);
    }
    sort(a, a+n, compare);
    dp[0] = -1;
    int ans=0;
    for (int i=0; i < n; i++)
    {
        if (a[i].second > dp[ans])
        {
            dp[++ans]=a[i].second;
        }
        else
        {
            int k = lower_bound(dp, dp+ans, a[i].second)-dp;
            dp[k] = a[i].second;
        }
    }
    cout << ans << endl;

    return 0;
}

春招到现在，笔试基本都是能A。但是面试总是差一点。还是要努力呀