一个问题
查看原帖
一个问题
1045201
shortintlonglong楼主2024/1/22 20:46
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N], x, n, maxn, g[N], cnt;
int main() {
	ios::sync_with_stdio(false); cin.tie(0);
    while (cin >> x) a[++ n] = x;
    g[0] = 2e9;
    for (int i = 1; i <= n; ++ i) {
        if (a[i] <= g[cnt]) g[++ cnt] = a[i];
        else {
            int l = 1, r = cnt;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] < a[i]) r = mid;
                else l = mid + 1;
            } g[l] = a[i];
        }
    } cout << cnt << endl;
    cnt = 0, g[0] = -2e9;
    for (int i = 1; i <= n; ++ i) {
        if (a[i] > g[cnt]) g[++ cnt] = a[i];
        else {
            int l = 1, r = cnt;
            while (l < r) {
                int mid = l + r >> 1;
                if (g[mid] >= a[i]) r = mid;
                else l = mid + 1;
            } g[l] = a[i];
        }
    } cout << cnt;
}

请问第一个 for 循环 如果 a[i] > g[cnt] 为什么 cnt 不用任何改变 (第一个 for 循环求的是a1-an的最长不升子序列,存储在cnt中)

2024/1/22 20:46
加载中...