Good subsequence
Problem's Link: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1553
Mean:
给你一个长度为n的序列和一个值k，让你找出一个子序列，满足在这个子序列中max-min的值<=k，求这个子序列最长的长度。
analyse:
这题做法很多，直接暴力枚举每一个数为起点。
Time complexity: O(n)
Source code:
方法一（暴力）：
// Memory Time // 1347K 0MS // by : crazyacking // 2015-03-30-16.02 #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define MAXN 1000010 #define LL long long using namespace std; int n,k; vector<int> ve; int main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen("C:\\Users\\Devin\\Desktop\\cin.cpp","r",stdin); // freopen("C:\\Users\\Devin\\Desktop\\cout.cpp","w",stdout); while(cin>>n>>k) { ve.clear(); for(int i=0;i<n;++i) { int tmp; cin>>tmp; ve.push_back(tmp); } int ans=1; for(int i=0;i<n;++i) { int cnt=1; int maxx=ve[i]; int minn=ve[i]; for(int j=i+1;j<n;++j) { if(ve[j]>=maxx) { maxx=ve[j]; } if(ve[j]<=minn) { minn=ve[j]; } if(maxx-minn>k) break; cnt++; } if(cnt>ans) ans=cnt; } cout<<ans<<endl; } return 0; } /* */
方法二(STL):
做法很巧妙，用一个multiset来维护：加入当前这个数后满足条件的连续子序列，也就是说每一轮循环set中的元素都是满足条件的。
// Memory Time // 1347K 0MS // by : crazyacking // 2015-03-30-15.53 #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<set> #include<string> #include<cstdlib> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define MAXN 1000010 #define LL long long using namespace std; int n,k; multiset<int> se; vector<int> ve; int main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen("C:\\Users\\Devin\\Desktop\\cin.cpp","r",stdin); // freopen("C:\\Users\\Devin\\Desktop\\cout.cpp","w",stdout); while(cin>>n>>k) { se.clear(); ve.clear(); for(int i=0;i<n;++i) { int tmp; cin>>tmp; ve.push_back(tmp); } int ans=1; for(int i=0,j=0;i<n;++i) { se.insert(ve[i]); for(;*se.rbegin()-*se.begin()>k;j++) { se.erase(ve[j]); } if(i-j+1>ans) ans=i-j+1; } cout<<ans<<endl; } return 0; } /* */
