感觉智力题错了几个。。
编程题两题 第一题字符串翻转。。这么弱智就不说了
第二题俄罗斯套娃
有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。但是面试总是差一点。还是要努力呀
