A
Description:
- 一叠卡牌有 \(n\) 张,每张卡牌上面写有一个数字,从上往下数第 \(i\) 张卡牌上面写的数字为 \(a_i\),每张卡牌上面写的数字互不相等,并且数字都在 \([1, n]\) 的范围内。现在要把卡牌整理成顺序卡牌(卡牌堆从上到下第 \(i\) 张卡牌上面写着数字 \(i\) )。 可是这叠卡牌被诅咒过,对卡牌的操作只能按以下规则执行:
- 选择牌堆中任意一张卡牌,从卡牌堆中抽出,并将其放置于牌堆顶。
- 请问最少需要执行几次这样的操作可以将卡牌整理成顺序卡牌
Constraints:
- \(1\le n \le 3 \times 10^5\)
- \(1\le a_i \le n\)
- \(\forall i,j(1\le i \lt j \le n)\),$a_i \neq a_j $
Analysis:
- 最多要进行 \(n-1\) 次操作,只要某个数比前面小,就要调整顺序,故可以从后遍历,找到最长的接续序列,如 \(n,n-1,n-2,···\),最小操作次数即为总长度减去该序列的长度。
Solution:
void solve() {
int n; cin >> n;
vector<int> v;
for(int i=0;i<n;i++) {
int x; cin >> x;
v.push_back(x);
}
int ans = n;
for(int i=n-1;i>=0;i--) {
if(v[i] == ans) ans --;
}
cout << ans << endl;
}
标签:le,数字,int,张卡牌,卡牌,ans,排序
From: https://www.cnblogs.com/Trilliverse/p/17826455.html