kaito_936 @ 2024-04-09 20:43:18
这个题目对时间不是很苛刻吗，所以我试了一个下午，包括偷看别人的代码，我就发现一个问题，为什么代码明明差不多，举个例子：这题不是用单调队列吗，我就用的一个数组，然后定义一个开始位置和结束位置。结果是耗时稳定在930ms，但是有个和我代码差不多的用的容器耗时640ms，然后我也就用了容器，但是还是稳定930ms，这是为什么啊（我还没有接触过数据结构与算法），纠结了我一个下午了。
#include<iostream>
#include<deque>
using namespace std;
int N, M, a1[2000001];
deque<int> arr;
int main()
{
cin >> N >> M;
printf("0\n");
for (int i = 1; i < N; i++) {
scanf_s("%d", a1 + i);
while ( !arr.empty()&& a1[arr.back()] >= a1[i]) arr.pop_back();
arr.push_back(i);
if (i - arr.front() == M) arr.pop_front();
printf("%d\n", a1[arr.front()]);
}
return 0;
}by EmptyAlien @ 2024-04-09 20:46:38
是不是没开 O2
by kaito_936 @ 2024-04-09 20:48:09
@Lightning_Creeper 开了，刚刚找了我对照的那位
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, k;
int a[N];
int p[N], q[N], head = 1, tail;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cout << q[head] << '\n';
while (head <= tail && q[tail] >= a[i]) {
--tail;
}
q[++tail] = a[i];
p[tail] = i;
while (head <= tail && p[head] < i - k + 1) {
++head;
}
}
return 0;
}by Po7ed @ 2024-04-09 20:48:57
@kaito_936 你没关 io 同步。
by Po7ed @ 2024-04-09 20:49:49
就是这玩意
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);可以提升 cin、cout 速度。
by kaito_936 @ 2024-04-09 20:49:56
@Lightning_Creeper 找错了，是这位
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
constexpr int N = 2e5 + 10;
constexpr int inf = (1ll << 31) - 1;
void solve()
{
int n,m; cin>>n>>m;
vector<int> v(n+1);
for(int i=1;i<=n;i++) cin>>v[i];
deque<int> q;
cout<<0<<"\n";
q.push_back(1);
for(int i=2;i<=n;i++){
while(!q.empty()&&i-q.front()>m) q.pop_front();
cout<<v[q.front()]<<"\n";
while(!q.empty()&&v[q.back()]>=v[i]) q.pop_back();
q.push_back(i);
}
return ;
}
signed main()
{
IOS;
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}by Po7ed @ 2024-04-09 20:50:50
这位也开了
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
...
IOS;by Po7ed @ 2024-04-09 20:51:19
@kaito_936
by kaito_936 @ 2024-04-09 20:51:21
@Lightning_Creeper 我这么粘代码应该不会出事吧。。。。
by kaito_936 @ 2024-04-09 20:53:57
@Po7ed 我去试试
by Po7ed @ 2024-04-09 20:56:48
@kaito_936 等等你用的是 C 风格输入输出（scanf & printf）。