题意：给你一个序列，问你最少移动多少个数使得数列不递减。
解题思路：其实就是要找到这个数列的最长不递减子序列。
解题代码：
1 // File Name: 269b.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月09日 星期一 18时44分02秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 int a[10000]; 28 int ans[10000]; 29 int n , m; 30 int Find(int l , int r, int x ) 31 { 32 while(l <= r ) 33 { 34 int m = (l + r)/2; 35 if(ans[m] <= x ) 36 { 37 l = m + 1; 38 }else { 39 r = m - 1; 40 } 41 } 42 return l; 43 } 44 int solve() 45 { 46 int t = 1; 47 ans[1] = a[1]; 48 for(int i = 2;i <= n;i ++) 49 { 50 if(a[i] >= ans[t]) 51 { 52 t ++ ; 53 ans[t] = a[i]; 54 }else{ 55 //printf("%d %d ",i,Find(1,t,a[i])); 56 ans[Find(1,t,a[i])] = a[i]; 57 } 58 /*for(int i = 1;i <= t;i ++) 59 printf("%d ",ans[i]); 60 printf(" ");*/ 61 } 62 return n - t; 63 } 64 int main(){ 65 scanf("%d %d",&n,&m); 66 double tmp ; 67 for(int i = 1;i <= n;i ++) 68 { 69 scanf("%d %lf",&a[i],&tmp); 70 } 71 printf("%d ",solve()); 72 return 0; 73 }