本文共 1546 字，大约阅读时间需要 5 分钟。

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

来源：牛客网

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

假设五座山峰的高度依次是3，4，3，2，1。从第一座山峰上放飞的纸飞机可以依次经过第一、四、五座山峰，但不能经过第二、三座山峰。 对于每座山峰，求出要经过除这座山峰外的每座山峰，至少需要放飞多少纸飞机。（每架纸飞机的起点可以不同） 输入描述: 第一行包括一个正整数n。

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

输出描述:

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

输出

2 3 3 3 2

备注:

1≤n≤106 1≤hi≤230 思路：这题其实就是最小链覆盖问题，最小链覆盖等于最长反链，于是就是求去掉i这个值以后的最长LIS的长度。以每个点i为结尾的最长LIS用树状数组很容易求，记为Max，但去点i位置的数后的最长LIS怎么求呢？我们可以判断一下每一位是不是有可能是最初的LIS上的点，如果这些点都是唯一的，不能被替换的话，那么答案就是Max-1，如果能替换就是Max；比如样例2 4 3 1 5，最长链可能是2 4 5，4是最长链上的一点，但是去掉4以后，还有3可以替换4的位置是不是？

#include
   
    #define lowbit(i) ((i)&(-i))using namespace std;const int maxn=1e6+1;int n,size,a[maxn],b[maxn],c[maxn],vis[maxn],vis2[maxn]={   0},cns[maxn]={   0},num[maxn],Max=0;void add(int x,int v){   	while(x<=size) c[x]=max(c[x],v),x+=lowbit(x);}int query(int x){   	int res=0;	while(x) res=max(res,c[x]),x-=lowbit(x);	return res;}int main(){      scanf("%d",&n);   for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];   sort(b+1,b+1+n);    size=unique(b+1,b+1+n)-b-1;   for(int i=1;i<=n;++i)   a[i]=lower_bound(b+1,b+1+size,a[i])-b;//离散化    for(int i=1;i<=n;++i)   num[i]=query(a[i])+1,add(a[i],num[i]),Max=max(Max,num[i]);//求到i这个位置为止的最长lIS    vis[Max+1]=1e9+1;   for(int i=n;i>=1;--i)   if(vis[num[i]+1]>=a[i])//判断它是不是最长LIS上的点    {      	vis[num[i]]=max(vis[num[i]],a[i]);vis2[i]=1;    }   for(int i=1;i<=n;++i)   if(vis2[i]) cns[num[i]]++;//统计一下这个数是否有重复，有重复的话就可以替换   for(int i=1;i<=n;++i) printf("%d ",Max-(vis2[i]&&cns[num[i]]==1)); }