搜索

洛谷-1020


发布时间: 2022-11-24 23:29:01    浏览次数:40 次

洛谷-1020

思路

由这篇blog可以知道本题求的就是 最长上升子序列 和 最长下降子序列 的长度。

采用的是\(O(nlogn)\)的做法。

有一个问题,在求最长上升子序列的过程中,用到了lower_bound函数,求第一个大于等于t的数;

这里不能使用upper_bound函数,因为它求的是第一个大于t的数字,所以遇到相同的数也会加入LIS中,实际上是错的。

同理,在求最长下降子序列的过程中,需要求第一个小于等于t的数,如何求呢?

由于lower_bound函数的第4个参数可以自己设置比较函数,考虑自定义比较函数cmp

自定义cmp

奇奇怪怪的less和greater。

lower_bound(,,t)求第一个大于等于t的数,相当于lower_bound(,,t,less<int>())

less完全相反的就是greater。即lower_bound(,,t,greater<int>())求的是第一个小于t的数。

由上可知lower_bound(,,t,less_equal<int>())求的是第一个大于t的数。

由上可知lower_bound(,,t,greater_equal<int>())求的是第一个小于等于t的数。

故,lower_bound(,,t,greater_equal<int>())就是我们寻找的比较函数。

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
// #define int long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;

vector<int> LIS, LDS;

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    int t;
    while (cin >> t) {
        int idx = lower_bound(LIS.begin(), LIS.end(),t,less<int>()) - LIS.begin();
        // 同理,可以换成upper_bound,通过less_equal实现小于等于t的第一个数。
        // int idx = upper_bound(LIS.begin(), LIS.end(),t,less_equal<int>()) - LIS.begin();
        if (idx == SZ(LIS)) {
            LIS.push_back(t);
        }
        else {
            LIS[idx] = t;
        }
        idx = lower_bound(LDS.begin(), LDS.end(),t, greater_equal<int>()) - LDS.begin();
        // 同理可以换成upper_bound,通过greater来实现小于等于t的第一个数。
        // idx = upper_bound(LDS.begin(), LDS.end(),t, greater<int>()) - LDS.begin();
        if (idx == SZ(LDS)) {
            LDS.push_back(t);
        }
        else {
            LDS[idx] = t;
        }
    }
    cout << SZ(LDS) << "\n" << SZ(LIS);

}
免责声明 洛谷-1020,资源类别:文本, 浏览次数:40 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 11:29:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/FanWQ/p/16916581.html