牛客挑战赛36 C 纸飞机，最小链覆盖，LIS+思维，详细题解

牛客挑战赛36 C 纸飞机 (最小链覆盖，LIS+思维，详细题解)

链接：https://ac.nowcoder.com/acm/contest/3782/C

来源：牛客网

纸飞机

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

直线上有n座山峰，第i座的高度为hi。从某座山峰上放飞一架纸飞机，它可以从左往右依次经过一系列高度严格递减的山头。

假设五座山峰的高度依次是3，4，3，2，1。从第一座山峰上放飞的纸飞机可以依次经过第一、四、五座山峰，但不能经过第二、三座山峰。

对于每座山峰，求出要经过除这座山峰外的每座山峰，至少需要放飞多少纸飞机。（每架纸飞机的起点可以不同）

输入描述:

第一行包括一个正整数n。第二行包括n个正整数，第i个数表示第i座山峰的高度hi。

输出描述:

输出一行，包括n个用空格隔开的正整数，第i个数表示除去第i座山峰的答案。

示例1

输入

[复制](javascript:void(0)????

5
2 4 3 1 5

输出

[复制](javascript:void(0)????

2 3 3 3 2

备注:

1≤n≤1061≤hi≤230

思路：

首先我们应该知道，最小链覆盖等于最长反链（反过来的最长不下降子序列）。

然后我们通过二分维护出以下两个数组：

\(f[i]\) 代表从左开始的以a[i] 结尾的 最长不下降子序列

$ b[i]$ 代表以a[i] 开始向右的最长不下降子序列

那么$ f[i]+b[i]-1 $ 就是包含a[i] 的 反向最长不下降子序列 长度

同时维护出最小链覆盖的值ans

那么删除a[i] 后的序列答案只有2种可能，ans 或 ans-1

如果a[i] 构成的反向最长不下降子序列 长度 是 ans，我们称之为腰点

1：如果a[i] 不是 腰点

那么删除后对序列的最小链覆盖没影响，所以答案是ans

2：如果a[i] 构成的反向最长不下降子序列 长度 是 ans

​ 1) 当 所以腰点 中 a[i] 的 f[i] 只出现一次，那么a[i] 是构成的反向最长不下降子序列的核心点，删除之后会使答案-1，所以答案为ans-1

​ 2) 当 所以腰点 中 a[i] 的 f[i] 出现多次，那么删除a[i] 后，会有其他 f[j]与f[i]相等的a[j]点代替掉a[i]的作用，所以答案仍为 ans

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
// HFUU-QerM
// 23:50:12
// HFUU-QerM
// 00:03:42

int n;
int a[maxn];
std::vector<int> p;
int f[maxn];
int b[maxn];
int cnt[maxn];

int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    n = readint();
    repd(i, 1, n)
    {
        a[i] = readint();
    }
    repd(i, 1, n)
    {
        int pos = upper_bound(ALL(p), a[i]) - p.begin() ;
        if (pos == sz(p))
        {
            p.push_back(a[i]);
        } else
        {
            p[pos] = a[i];
        }
        f[i] = pos + 1;
    }
    p.clear();
    for (int i = n; i >= 1; --i)
    {
        int pos = upper_bound(ALL(p), -a[i]) - p.begin() ;
        if (pos == sz(p))
        {
            p.push_back(-a[i]);
        } else
        {
            p[pos] = -a[i];
        }
        b[i] = pos + 1;
    }
    int ans = 0;
    repd(i, 1, n)
    {
        ans = max(ans, b[i] );
    }
    repd(i, 1, n)
    {
        if (f[i] + b[i] - 1 == ans)
        {
            cnt[f[i]]++;
        }
    }
    int out;
    repd(i, 1, n)
    {
        if (f[i] + b[i] - 1 == ans)
        {
            if (cnt[f[i]] > 1)
            {
                out = ans;
            } else
            {
                out = ans - 1;
            }
        } else
        {
            out = ans;
        }
        printf("%d%c", out, i == n ? '\n' : ' ' );
    }

    return 0;
}