【题目大意】:给出n个数c;求每k个数之间的最大最小值。
【解题思路】:今晚精神状态不太好c;本来是想来切切水题就睡觉的。谁知道写个单调队列G++还一直tle...不知道怎么class="tags" href="/tags/YouHua.html" title=优化>优化了c;不过幸运的是C++过了。
ce:pre">谁能告诉我G++要怎么改才能够过。
ce:pre">等明后天什么时候手痒写个线段树试试。
【代码】:
<code class="language-cpp">#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <string> #include <cctype> #include <map> #include <iomanip> using namespace std; #define eps 1e-8 #define pi acos(-1.0) #define inf 1<<30 #define pb push_back #define lc(x) (x << 1) #define rc(x) (x << 1 | 1) #define lowbit(x) (x & (-x)) #define ll long long int n,m; int a[1000010],maxx[1000010],minn[1000010]; void solve_maxx(){ int st=0,en=0; for(int i=0; i<m; i++){ while(a[maxx[en]]<a[i] && en>=st) en--; en++; maxx[en]=i; } printf("%d ",a[maxx[st]]); for(int i=m; i<n; i++){ while(maxx[st]<=i-m && st<=en) st++; while(a[maxx[en]]<a[i] && en>=st) en--; en++; maxx[en]=i; if(i!=n-1) printf("%d ",a[maxx[st]]); } printf("%d\n",a[maxx[st]]); } void solve_minn(){ int st=0,en=0; for(int i=0; i<m; i++){ while(a[minn[en]]>a[i] && en>=st) en--; en++; minn[en]=i; } printf("%d ",a[minn[st]]); for(int i=m; i<n; i++){ while(minn[st]<=i-m && st<=en) st++; while(a[minn[en]]>a[i] && en>=st) en--; en++; minn[en]=i; if(i!=n-1) printf("%d ",a[minn[st]]); } printf("%d\n",a[minn[st]]); } int main() { while (~scanf("%d%d",&n,&m)){ for (int i=0; i<n; i++) scanf("%d",&a[i]); solve_minn(); solve_maxx(); } return 0; } code>