dsl2002 @ 2017-01-25 18:32:10
一道一样的题,一份一样的代码,放在洛谷和另一个oj上AC,但在POJ上怎么会TLE啊??
···cpp
#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;
const int maxn = (int)1e6 + 5;
struct point {
int a, t;
};
deque<point> dmin, dmax;
int a[maxn], Min[maxn], Max[maxn];
int n, k;
int main()
{
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
int i;
scanf("%d%d", &n, &k);
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(i = 1; i <= n; i++) {
while(!dmax.empty() && dmax.back().a <= a[i])
dmax.pop_back();
dmax.push_back((point){a[i], i});
while(!dmin.empty() && dmin.back().a >= a[i])
dmin.pop_back();
dmin.push_back((point){a[i], i});
if(i >= k) {
Min[i - k + 1] = dmin.front().a; Max[i - k + 1] = dmax.front().a;
if(dmin.front().t <= i - k + 1) dmin.pop_front();
if(dmax.front().t <= i - k + 1) dmax.pop_front();
}
}
for(i = 1; i <= n - k + 1; i++)
printf("%d ", Min[i]);
printf("\n");
for(i = 1; i <= n - k + 1; i++)
printf("%d ", Max[i]);
return 0;
}
···
by afsg @ 2017-01-25 20:20:37
只能说明poj数据神
by litble @ 2017-06-20 15:01:05
在poj上G++会T改成C++就好了.....