题目大意

有 $n$ 颗行星，求从 $1$ 出发到 $n$ 所需最少加注次数，无解输出 $0$。

思路

考虑贪心，发现每次选可以走到最远的 $i$ 加注最优。 :::info[证明] 因为可以在中途停下，所以每次选走到最远的包含了所有情况。假设在一次飞行中，没选最优情况，而选了 $j$，其中 $a_j<a_i$，则本来当前最大到达区间 $[1,a_i]$，而现在只有 $[1,a_j]$，若下次加注的位置在 $(a_j,a_i]$，那么在 $j$ 加注没法保证最优。 ::: 预处理 $v[i]$ 表示 $i$ 之后第一个与 $i$ 同类型的位置。

初始区间 $[l=1,r=v_i]$，$1$ 已加注。

每次在 $(l, r]$ 中找 $v_i$ 的最大值，设 $k$ 表示 $v_i$ 最大的 $i$。

若最大值 $\le r$ 则无解。

否则加注 $k$，更新 $r=v[k]$，继续。

当 $r=n$ 时结束。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[300005],u[300005],v[300005],l=1,r,k=1,s=1,d;
vector<ll> t;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		v[u[a[i]]]=i;
		u[a[i]]=i;//u表示上一个a[i]的下标
	}
	r=v[1];//初始区间右端点
	t.push_back(1);//记录加注路径
	while(1){
		if(r==n){//达到n
			printf("%lld\n",s);
			for(int i=0;i<t.size();i++)printf("%lld ",t[i]);
			break;
		}
		d=0;//记录a[i]最大值
		while(l<r){
			l++;//l不会退，一路扫到r
			if(v[l]>d){
				d=v[l];
				k=l;//k记录最大i
			}
		}
		if(d<=r){//无解
			printf("0");
			break;
		}
		t.push_back(k);//最优选择k放入加注路径
		s++;
		r=d;
	}
	return 0;
}