hytallenxu @ 2024-01-13 22:02:01
rt,以下是我的暴力代码:
#include <iostream>
#include <cstring>
using namespace std;
int mini[1000010],maxi[1000010];
int main(){
int n,a[1000010],k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
mini[i]=1e9;
maxi[i]=-1e9;
}
for(int i=1;i<=n-k+1;i++){
if((a[i-1]==mini[i-1] or a[i-1]==maxi[i-1] or a[i+k-2]==mini[i-1] or a[i+k-2]==maxi[i-1]) or (mini[i-1]==0 or maxi[i-1]==0) or (a[i]<mini[i-1] or a[i]>maxi[i-1] or a[i+k-1]<mini[i-1] or a[i+k-1]>maxi[i-1])) {
for(int j=i;j<=i+k-1;j++) {
mini[i]=min(mini[i],a[j]);
maxi[i]=max(maxi[i],a[j]);
}
}else{
mini[i]=mini[i-1];
maxi[i]=maxi[i-1];
}
}
for(int i=1;i<=n-k+1;i++) cout<<mini[i]<<" ";
cout<<"\n";
for(int i=1;i<=n-k+1;i++) cout<<maxi[i]<<" ";
return 0;
}
然后他过了,评测记录
by hytallenxu @ 2024-01-13 22:02:23
甚至快读都没加
by hytallenxu @ 2024-01-13 22:18:14
暴力使用快读记录 --558ms
正解使用快读记录 --666ms
难道这就是暴力踩标算
by Expert_Dream @ 2024-01-13 22:22:30
啊?
by Expert_Dream @ 2024-01-13 22:24:25
@hytallenxu 就是说你那个if判断很玄学,删了之后 TLE * 1
by Expert_Dream @ 2024-01-13 22:26:57
@hytallenxu 你的代码时间复杂度是
by hytallenxu @ 2024-01-13 22:27:33
@gsczl71 ok 谢谢大佬
by hytallenxu @ 2024-01-13 22:28:34
@gsczl71 但是这样不就是1e6了吗,还是可以过吧 awa
by Expert_Dream @ 2024-01-13 22:30:39
@hytallenxu 不对,是n^2/k吧
我是那么认为,你每次得要最劣情况得要跳k步?还是咋样,我感觉我也不太清楚了。
by hytallenxu @ 2024-01-13 22:36:01
@gsczl71 hh
https://www.luogu.com.cn/problem/U397530
按照您的说法造了,但是就 269ms
by hytallenxu @ 2024-01-13 22:36:23
@gsczl71 没关流同步甚至