链接：https://www.luogu.com.cn/problem/P1020
这个题目一分为二：
首先就是LIS：改下，改成最长不升子序列，复杂度：nlogn;然后用vector的贪心，复杂度：n^2(这里似乎可以二分降到nlogn，不过反正过了OwO!)
被这个输入卡的好难受，建议用getline读取不确定的数
题目：
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef unsigned long long ll;
using namespace std;
const int N = 1e5 + 5;
ll v[N];
ll jd[N];
int binarysearch(int l, int r, int val)
{
int ll = l, rr = r, mid;
while (ll < rr)
{
mid = ll + (rr - ll) / 2;
if (val <= jd[mid])ll = mid + 1;
else rr = mid;
}
return ll;
}
int toa(string s)//getline配套
{
int ans = 0;
for (int i = 0; i < s.length(); i++)ans = ans * 10 + s[i] - '0';
return ans;
}
int main()
{
string s;
int n = 0;
getline(cin, s);
int lef = 0, righ = 1;
while (righ < s.length())
{
while (righ < s.length() and s[righ] != ' ')righ++;
v[++n] = toa(s.substr(lef, righ-lef));
lef = righ + 1;
righ = lef;
}
for (int i = 1; i <= n; i++)jd[i] = LLONG_MAX;
jd[1] = v[1];
ll ans = 1;
//标准的LIS模板
for (int i = 2; i <= n; i++)
{
if (v[i] <= jd[ans])
{
ans++; jd[ans] = v[i];
}
else jd[binarysearch(1, ans, v[i])] = v[i];
}
cout << ans << endl;
vector<int>num2;
num2.push_back(v[1]);
//标准的贪心，求第二问
for (int i = 2; i <= n; i++)
{
if (num2.back() < v[i])num2.push_back(v[i]);
else
for(int j=0;j<num2.size();j++)
if (num2[j] >= v[i])
{
num2[j] = v[i];
break;
}
}
cout << num2.size();
return 0;
}