Mingxuan @ 2019-09-16 23:36:20
//
// Created by Xianzhu Yue on 2019-09-12.
//
#include <stdio.h>
#define INF 0x7fffffff
int min(int x,int y){return x>y?y:x;}
int max(int x,int y){return x>y?x:y;}
int main()
{
//std::cout << "Hello, World!" << std::endl;
int a,b;
scanf("%d%d",&a,&b);
int c[a+1],c1[a-b+2],c2[a-b+2],d[b+1],e=1,n=a-b+1;
for(int i=0;i<a;i++)
{
scanf("%d",&c[i]);
if(i<b) d[i]=c[i];
}
while(n--)
{
int ans=INF,ans2=-INF;
for(int i=0;i<b;i++)
{
ans=min(ans,d[i]);
ans2=max(ans2,d[i]);
d[i]=c[i+e];
}
c1[e-1]=ans;
c2[e-1]=ans2;
e++;
}
for(int i=0;i<e-1;i++)
printf("%d ",c1[i]);
printf("\n");
for(int i=0;i<e-1;i++)
printf("%d ",c2[i]);
return 0;
}by Mingxuan @ 2019-09-16 23:36:42
8.9.10 TLE
by Ludo @ 2019-09-16 23:41:48
DP+单调队列优化 或 线段树
by 静谧时空 @ 2019-09-16 23:43:24
@Mingxuan
学一下单调队列吧
好久以前的代码
自己看吧
#include <cstdio>
#include <deque>
using namespace std;
const int N=1000005;
int n,k;
int v[N];
deque<int>q;
void maintain_less(int now) {
while(!q.empty()&&q.back()+k<=now) q.pop_back();
while(!q.empty()&&v[q.front()]>v[now]) q.pop_front();
q.push_front(now);
}
void maintain_more(int now) {
while(!q.empty()&&q.back()+k<=now) q.pop_back();
while(!q.empty()&&v[q.front()]<v[now]) q.pop_front();
q.push_front(now);
}
int main() {
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<k;i++)
maintain_less(i);
for(int i=k;i<=n;i++) {
maintain_less(i);
printf("%d ",v[q.back()]);
}
while(!q.empty()) q.pop_front();
printf("\n");
for(int i=1;i<k;i++)
maintain_more(i);
for(int i=k;i<=n;i++) {
maintain_more(i);
printf("%d ",v[q.back()]);
}
return 0;
}by 静谧时空 @ 2019-09-16 23:44:04
这也可以用st表做
by HaveFun @ 2019-09-16 23:47:46
@静谧时空 线段树也可以鸭（只是要卡常qwq）
by MZW_BG @ 2019-09-17 09:55:55
同学您的算法应该优化一下，单靠卡常是没有出路的
别人AC的代码一般都是100ms以内的，但是你在前面的点就已经200+ms了
by MZW_BG @ 2019-09-17 09:57:53
当然你想卡的话也可以卡
你这还有很大的优化空间，比如fread,register,Ofast什么的都可以
使用__asm转为汇编语言会获得极大的常数提升
by Mingxuan @ 2019-09-18 13:44:08
@MZW_BG 稍微优化了一下，过了，共计944ms
//
// Created by Xianzhu Yue on 2019-09-12.
//
#include <stdio.h>
#define INF 0x7fffffff
int min(int x,int y){return x>y?y:x;}
int max(int x,int y){return x<y?y:x;}
int main()
{
//std::cout << "Hello, World!" << std::endl;
int a,b,ans=INF;
scanf("%d%d",&a,&b);
int c[a+1],c1[a-b+2],c2[a-b+2];
int n=a-b+1,v=n,k=0,t=0,bj=0;
for(int i=0;i<a;i++)
{
scanf("%d",&c[i]);
}
while(n--)
{
while(k<b)
{
ans=min(ans,c[k]);
k++;
}
if(bj==0)
{
c1[t]=ans;
t++;
bj=1;
}
if(ans!=c[t-1])
{
ans=min(ans,c[t-1+b]);
c1[t]=ans;
t++;
}
else
{
ans=INF;
for(int i=t;i<t+b;i++)
{
ans=min(ans,c[i]);
}
c1[t]=ans;
t++;
}
k++;
}
bj=0;
int k2=0;
int t2=0,ans2=-INF;
//printf("%d\n",b);
while(v--)
{
while(k2<b)
{
ans2=max(ans2,c[k2]);
//printf("%d %d %d\n",k,c[k],ans2);
k2++;
}
if(bj==0)
{
c2[t2]=ans2;
// printf("[ %d ]",ans2);
t2++;
bj=1;
}
if(ans2!=c[t2-1])
{
ans2=max(ans2,c[t2-1+b]);
c2[t2]=ans2;
t2++;
}
else
{
ans2=-INF;
for(int i=t2;i<t2+b;i++)
{
ans2=max(ans2,c[i]);
}
c2[t2]=ans2;
t2++;
}
k2++;
}
for(int i=0;i<t-1;i++)
{
printf("%d ",c1[i]);
}
printf("\n");
for(int i=0;i<t2-1;i++)
{
printf("%d ",c2[i]);
}
return 0;
}by MZW_BG @ 2019-09-18 13:54:02
@Mingxuan 您这代码我看的不是很懂……
另外int c[a+1]这种形式不是很好吧……很容易爆栈了啦
by Mingxuan @ 2019-09-18 19:01:54
@MZW_BG
洛谷支持这样，我数组应该不会爆的，因为a最大也就10^6，洛谷中关键字不判错