題意：給你一個序列，問你最少移動多少個數使得數列不遞減。

解題思路：其實就是要找到這個數列的最長不遞減子序列。

解題代碼：

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\n",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("\n");*/ 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\n",solve()); 72 return 0; 73 } View Code

?

轉載于:https://www.cnblogs.com/zyue/p/4324381.html

總結

以上是生活随笔為你收集整理的codeforces 269B Greenhouse Effect的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。