gjr0128 @ 2023-10-18 21:37:09
代码如下
#include<bits/stdc++.h>
using namespace std;
long long a[10000000];
vector<long long>v;
void pan(long long num1,long long x,long long k)
{
num1=a[x];
for(int i=x;i<(x+k-1);i++)
{
if(num1<a[i+1])
{
num1=a[i+1];
}
else
{
continue;
}
}
cout<<num1<<" ";}
void pan2(long long num2,long long x,long long k)
{
num2=a[x];
for(int i=x;i<(x+k-1);i++)
{
if(num2>a[i+1])
{
num2=a[i+1];
}
else
{
continue;
}
}
cout<<num2<<" ";}
int main()
{
long long n,k;
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
v.push_back(a[i]);
}
for(int i=0;i<n;i++)
{
if(i>(n-k))
{
continue;
}
pan2(0,i,k);
}
cout<<endl;
for(int i=0;i<n;i++)
{
if(i>(n-k))
{
continue;
}
pan(0,i,k);
}
return 0;
} 我也开了O2 有没有大佬教教我。
by lao_wang @ 2023-10-18 21:39:41
#include<bits/stdc++.h>
using namespace std ;
long long n , a[5234456] , k ;
struct node {
long long minn , maxn , l , r ;
} tree[4444444];
void up(long long num) {
tree[num].minn = min(tree[num<<1].minn,tree[num<<1|1].minn) ;
tree[num].maxn = max(tree[num<<1].maxn,tree[num<<1|1].maxn) ;
}
void made(long long num,long long l,long long r) {
tree[num].l = l ;
tree[num].r = r ;
tree[num].minn = 1e+13 ;
tree[num].maxn = -1e+13 ;
if(l==r) {
tree[num].maxn = a[l] ;
tree[num].minn = a[l] ;
return ;
}
made(num<<1,l,(l+r)>>1) ;
made(num<<1|1,((l+r)>>1)+1,r) ;
up(num) ;
}
long long ask1(long long num,long long l,long long r) {
// cout << num << " " ;
long long maxn=-1e+12 ;
if(tree[num].l>=l&&tree[num].r<=r) {
return tree[num].maxn ;
}
long long mid = (tree[num].l+tree[num].r)>>1 ;
if(mid>=l)
maxn = max(maxn,ask1(num<<1,l,r)) ;
if(mid+1<=r)
maxn = max(maxn,ask1(num<<1|1,l,r)) ;
return maxn ;
}
long long ask2(long long num,long long l,long long r) {
// cout << num << " " ;
long long minn=1e+12 ;
if(tree[num].l>=l&&tree[num].r<=r) {
return tree[num].minn ;
}
long long mid = (tree[num].l+tree[num].r)>>1 ;
if(mid>=l)
minn = min(minn,ask2(num<<1,l,r)) ;
if(mid+1<=r)
minn = min(minn,ask2(num<<1|1,l,r)) ;
return minn ;
}
int main() {
// freopen("window.in","r",stdin) ;
// freopen("window.out","w",stdout) ;
cin >> n >> k ;
for(int i=1; i<=n; i++) {
scanf("%lld",a+i) ;
}
made(1,1,n) ;
long long l=1 , r=k ;
while(r<=n) {
long long temp2=ask2(1,l,r) ;
cout << temp2 << " " ;
l++ , r++ ;
}
cout << endl ;
l=1 , r=k ;
while(r<=n) {
long long temp1=ask1(1,l,r) ;
cout << temp1 << " " ;
l++ , r++ ;
}
return 0 ;
}
/*
cin:5
1 5 2 4 3
cout: 55 35 23 15 5
*/by _zhx @ 2023-10-18 21:39:41
@gjr0128 你这看起来怪怪的，没必要这么复杂
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k,a[N],q[N],tt=-1,hh=0;
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
if(hh<=tt&&-k<i-q[hh]+1) hh++;
while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
cout<<'\n';
tt=-1,hh=0;
for(int i=0;i<n;i++)
{
if(hh<=tt&&i-k+1>q[hh]) hh++;
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<" ";
}
return 0;
}by gjr0128 @ 2023-10-18 21:41:27
@_zhx好的，我去改下。
by Chlero @ 2023-10-19 20:12:55
@gjr0128 建议重写
by gjr0128 @ 2023-10-19 20:27:54
@sketchi 你不是在学校跟我说了吗？我知道了。
by liwenliwenllll @ 2023-11-11 01:59:26
@gjr0128 能问下你是测试点2过不了吗，我也想知道我的代码为什么过不了
by gjr0128 @ 2023-11-11 08:24:38
@liwenliwenllll 并不是第2个不过而是第9个会TLE
by liwenliwenllll @ 2023-11-13 00:23:09
@gjr0128 我一开始单调队列判断是
while(!q.empty()&&arr[i]<q.back()
但是这里队列里面放的是下标也就是说我拿值跟下标在比较，应该是： while(!q.empty()&&arr[i]<arr[q.back()])
现已过，栓Q