题解 P6549 【[COCI2010-2011#2] KNJIGE】

### 题目大意 给出序列a，每次操作将序列中的任意一个元素移动到最前面，求使序列有序的最小操作次数。 ### 分析 首先，我们假设所有元素“完全无序”，例如序列：{ 8，7，6，5，4，3，2，1 }，则此时需要进行操作的次数就是 7 次（只有 8 不被移动）。而如果我们将编号最大的书向前移动，变成 { 7，8，6，5，4，3，2，1 } ，可以不被移动的书就变成了 7、8 两本。由此我们可以发现 **已经按照有序的顺序摆放的书本不用被移动。** 但是这还不够，我们来看这个序列：{ 7，1，2，3，4，5，6，8 }。我们发现，尽管这个序列中的 1，2，3，4，5，6 已经按照字典序摆放好了，但是我们依然要进行 6 次操作才能达成目标。因为元素“8”之前的有序元素“7”并没有被正确摆放。所以我们可以得到：**按字典序从大到小排列时，字典序较大的元素与其前一个有序元素之间的所有元素都需要被移动。** 通过以上分析，我们就可以得出本题的解法：**从后向前遍历整个序列，从字典序最大的元素开始，依次按字典序从大到小统计所有已经按顺序摆放的元素，这些元素就可以不被操作。** 分析结束，上代码！ ### Code ```cpp #include<bits/stdc++.h> using namespace std; int n,ans; int a[300005]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ans=n; for(int i=n;i>=1;i--) if(a[i]==ans) //先假设所有书都需要被操作，ans=n， ans--; //找到不需要被操作的书后ans--; printf("%d",ans); } ``` 完结撒fa~