- 问答
- 2015-07-09 15:12:24 @
最近在我们老师做的网站上做了有一道题,我和我同学都是cout能过,printfTLE。请问一下这是为什么?!一般来讲不应该是printf更快一些么?!
下面我把题目和我写的代码贴上去
给你一个长度为 N 的数组,一个长为 K 的滑动的窗体从最左移至最右端,你只能见到窗口的 K 个整数,每次窗体向右移动一位,如下表:
你的任务是找出窗口在各位置时的最大值和最小值。
输入格式
输入的第 1 行是两个整数 n,k,第 2 行为长度为 n 的数组(即有 n 个整数)。
输出格式
输出 2 行,第 1 行是每个位置的最小值,第 2 行是每个位置的最大值。
样例数据 1
输入 [复制]
8 3
1 3 -1 -3 5 3 6 7
输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
备注
【数据范围】
对于 20% 的数据:n<=500;
对于 50% 的数据:n<=100000;
对于 100% 的数据:n<=1000000;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<string>
#define maxn 1000005
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
using namespace std;
int n,k,mi,ma,num;
int cha[maxn];
int ans[maxn];
struct node
{
int l;
int r;
int minn;
int maxx;
}tree[3*maxn];
inline int getint()
{
int _b=0;char _c;int _p=1;
for (_c=getchar();(_c<'0'||_c>'9')&&_c!='-';_c=getchar());
if(_c=='-')
{
_c=getchar();
_p=-1;
}
for (;_c>='0'&&_c<='9';_c=getchar())
{
_b=(_b<<3)+(_b<<1);
_b+=_c-'0';
}
return _p*_b;
}
inline void build(int l,int r,int v)
{
tree[v].l=l;
tree[v].r=r;
if(l==r)
{
tree[v].minn=cha[r];
tree[v].maxx=cha[r];
return;
}
int mid=(l+r)>>1;
build(l,mid,v<<1);
build(mid+1,r,v<<1|1);
tree[v].maxx=max(tree[v<<1].maxx,tree[v<<1|1].maxx);
tree[v].minn=min(tree[v<<1].minn,tree[v<<1|1].minn);
}
inline void query(int l,int r,int v)
{
if(tree[v].l>=l&&tree[v].r<=r)
{
mi=min(mi,tree[v].minn);
ma=max(ma,tree[v].maxx);
return;
}
if(tree[v].l==tree[v].r)
return;
int mid=(tree[v].l+tree[v].r)>>1;
if(r<=mid)
query(l,r,v<<1);
else
if(l>mid)
query(l,r,v<<1|1);
else
{
query(l,mid,v<<1);
query(mid+1,r,v<<1|1);
}
}
int main()
{
freopen("sliding.in","r",stdin);
freopen("sliding.out","w",stdout);
n=getint();
k=getint();
for(int i=1;i<=n;i++)
cha[i]=getint();
build(1,n,1);
for(int i=1;i<=n-k+1;i++)
{
mi=1000000000;
ma=-1000000000;
query(i,i+k-1,1);
printf("%d ",mi);
ans[++num]=ma;
}
printf("\n");
for(int i=1;i<=num;i++)
printf("%d ",ans[i]);
return 0;
}
1 条评论
-
Rachelselfish LV 8 @ 2015-07-09 15:12:53
poj2823 limited time 1s
- 1