STL带来的问题?

P1439 【模板】最长公共子序列

orgn @ 2021-12-25 21:35:26

不知道哪有问题……

#include <bits/stdc++.h>
using namespace std;
struct node {
    int na, be;
} p[1000005];
int n, f[1000005], len = 0;
bool cmp ( node a, node b ) {
    return a.be < b.be;
}
inline int read() {
    int k = 0;
    char ch = getchar();
    while ( ch < '0' || ch > '9' ) ch = getchar();
    while ( ch >= '0' && ch <= '9' ) k = k * 10 + ( ch - '0' ), ch = getchar();
    return k;
}
int main () {
    //  freopen(".in","r",stdin);
    //  freopen(".out","w",stdout);
    n = read();
    for ( int i = 1; i <= n; i++ ) p[i].be = read();
    for ( int i = 1; i <= n; i++ ) p[i].na = read();
    sort ( p + 1, p + 1 + n, cmp );
    for ( int i = 1; i <= n; i++ ) cout<<p[i].be<<" "; cout<<endl;
    for ( int i = 1; i <= n; i++ ) cout<<p[i].na<<" "; cout<<endl;
    f[++len] = p[1].na;
    for ( int i = 2; i <= n; i++ ) {
        if ( p[i].na > f[len] ) f[++len] = p[i].na;
        else f[lower_bound ( f + 1, f + 1 + len, p[i].na ) - f] = p[i].na;
    }
    cout<<endl;
    for(int i=1;i<=len;i++) cout<<f[i]<<" ";
    cout<<endl;
    cout << len << endl;
    return 0;
}

by y_kx_b @ 2022-10-13 14:11:27

@orgn

  1. 你调试代码没删()
  2. for ( int i = 1; i <= n; i++ ) p[i].be = read();
    for ( int i = 1; i <= n; i++ ) p[i].na = read();
    sort ( p + 1, p + 1 + n, cmp );

    这样写是错误的。可以自己证。


|