AC了但仍有疑问
查看原帖
AC了但仍有疑问
1288371
abc123_cn楼主2025/7/3 11:40

92pts:

#include <bits/stdc++.h>
using namespace std;

int a[500005], b[500005], f[500005], maxn, cnt = 0, len = 1;

bool check(int x, int y)
{
    return b[x] <= a[y];
}

int main()
{
    while (cin >> a[++ cnt]) {}
    cnt --;
    b[len] = a[1];
    for (int i = 2; i <= cnt; i ++)
    {
        if (b[len] >= a[i]) b[++ len] = a[i];
        else
        {
            int x = 1, y = cnt;
            while (x < y)
            {
                int mid = (x + y) / 2;
                if (check(mid, i)) y = mid;
                else x = mid + 1;
            }
            b[x] = a[i];
        }
    }
    cout << len << endl;
    
    int k = 0;
    for (int i = 1; i <= cnt; i ++)
    {
    	bool vis = false;
    	for (int j = 1; j <= k; j ++)
    		if (a[i] <= f[j]) 
    		{
    			f[j] = a[i];
    			vis = true;
                break;
    		}
    	if (!vis) f[++ k] = a[i]; 
    }
    cout << k << endl;
}

为什么把check函数的return b[x] <= a[y];改成return b[x] < a[y]就AC了

2025/7/3 11:40
加载中...