Arup has just created a data structure that makes the two following list transformations in constant O(1) time:
a. Take any element in the list and move it to the front.
b. Take any element in the list and move it to the back.
You've realized that sorting speed can be improved using these transformations. For example, consider the input list:
8, 3, 6, 7, 4, 1, 5, 2
We can do the following sequence of transformations to sort this list:
8, 3, 7, 4, 1, 5, 2, 6 (move 6 to end)
8, 3, 4, 1, 5, 2, 6, 7 (move 7 to end)
2, 8, 3, 4, 1, 5, 6, 7 (move 2 to front)
1, 2, 8, 3, 4, 5, 6, 7 (move 1 to front)
1, 2, 3, 4, 5, 6, 7, 8 (move 8 to end).
You are now curious. Given an input array of distinct values, what is the fewest number of these first/last operations necessary to sort the array?
The Problem:
Given an initial permutation of the integers 1, 2, ..., n, determine the fewest number of first/last operations necessary to get the list of values sorted in increasing order.
The Input:
The first line of input will contain a single positive integer, n (n ≤ 1e5), representing the number of values to be sorted. The next n lines contain one integer each. All of these integers will be distinct values in between 1 and n (inclusive), representing the original order of the data to sort for the input case.
The Output:
On a line by itself, output the fewest number of first/last operations necessary to sort the input list.
题目大意与分析
对于一串数字，每次操作可以把任意一个数字移到最前或最后，问排序需要多少次操作
由于题目中说数字是1-n的每一个数字，所以可以找出其中最长的连续序列 例如41293587，其中123是不需要动的，剩下的依次往后排即可
#include <bits/stdc++.h> using namespace std; long long anss=0,i,n,j,a[100005],dp[100005]; int main() { cin>>n; for(i=0;i<n;i++) { cin>>a[i]; } for(i=0;i<n;i++) { dp[a[i]]=dp[a[i]-1]+1; anss=max(dp[a[i]],anss); } cout<<n-anss<<endl; }