hiro653 @ 2022-11-17 09:39:05
因为数的范围是int，在记录窗口内元素的个数的时候使用了map，超时了4个点，这是为什么呢,这个算法应该是
//#include <bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
//大根
priority_queue <int,vector<int>,greater<int>>q_sml;
//大根堆
priority_queue<int> q_big;
int p[1000005];
int sml[1000005];
int big[1000005];
int cnt=0;
map<int,int> mp;
int main() {
int n,k;
cin>>n>>k;
for(int i=1;i<=k;i++){
scanf("%d",&p[i]);
mp[p[i]]++;
q_big.push(p[i]);
q_sml.push(p[i]);
}
sml[++cnt]=q_sml.top();
big[cnt]=q_big.top();
//v_s.push_back(q_sml.top());
//v_b.push_back(q_big.top());
//cout<<q_sml.top()<<' '<<q_big.top()<<endl;
for(int i=k+1;i<=n;i++){
scanf("%d",&p[i]);
mp[p[i-k]]--;
mp[p[i]]++;
q_sml.push(p[i]);
q_big.push(p[i]);
while(!q_sml.empty()&&mp[q_sml.top()]==0){
q_sml.pop();
}
while(!q_big.empty()&&mp[q_big.top()]==0){
q_big.pop();
}
sml[++cnt]=q_sml.top();
big[cnt]=q_big.top();
//v_s.push_back(q_sml.top());
//v_b.push_back(q_big.top());
//cout<<q_sml.top()<<' '<<q_big.top()<<endl;
}
for(int i=1;i<=cnt;i++){
printf("%d ",sml[i]);
}
cout<<endl;
for(int i=1;i<=cnt;i++){
printf("%d ",big[i]);
}
}by xingke233 @ 2022-11-17 09:43:01
@hiro653
map 常数较大
手写 hash 试试
by hiro653 @ 2022-11-17 09:45:27
@xingke233 QAQ
by xingke233 @ 2022-11-17 10:13:27
@hiro653
把记录元素改为记录元素下标。
将map改为桶。
//#include <bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
//大根
int p[1000005];
int sml[1000005];
int big[1000005];
int cnt=0;
int d[1000005];
struct node1{
ll d;
bool operator<(const node1 &a) const{
return p[d]>p[a.d];
}
};
struct node{
ll d;
bool operator<(const node &a) const{
return p[d]<p[a.d];
}
};
priority_queue<node1>q_sml;
//大根堆
priority_queue<node> q_big;
int main() {
int n,k;
cin>>n>>k;
for(int i=1;i<=k;i++){
d[i]=1;
scanf("%d",&p[i]);
q_big.push({i});
q_sml.push({i});
}
sml[++cnt]=q_sml.top().d;
big[cnt]=q_big.top().d;
//v_s.push_back(q_sml.top());
//v_b.push_back(q_big.top());
//cout<<q_sml.top()<<' '<<q_big.top()<<endl;
for(int i=k+1;i<=n;i++){
scanf("%d",&p[i]);
d[i-k]=0;
d[i]=1;
q_sml.push({i});
q_big.push({i});
while(!q_sml.empty()&&d[q_sml.top().d]==0){
q_sml.pop();
}
while(!q_big.empty()&&d[q_big.top().d]==0){
q_big.pop();
}
sml[++cnt]=q_sml.top().d;
big[cnt]=q_big.top().d;
//v_s.push_back(q_sml.top());
//v_b.push_back(q_big.top());
//cout<<q_sml.top()<<' '<<q_big.top()<<endl;
}
for(int i=1;i<=cnt;i++){
printf("%d ",p[sml[i]]);
}
cout<<endl;
for(int i=1;i<=cnt;i++){
printf("%d ",p[big[i]]);
}
return 0;
}复杂度为 nlogn
by hiro653 @ 2022-11-17 10:19:43
@xingke233 好的，谢谢你！>_<!
by xingke233 @ 2022-11-17 10:27:29
@hiro653
将 map 改为 unordered_map 也可以通过。
但必须要 c++11 以上。
#include <bits/stdc++.h>
#include<unordered_map>
#include <unordered_map>
using namespace std;
typedef long long ll;
//大根
priority_queue <int,vector<int>,greater<int> >q_sml;
//大根堆
priority_queue<int> q_big;
int p[1000005];
int sml[1000005];
int big[1000005];
int cnt=0;
int main() {
std::unordered_map<int,int> ma;
int n,k;
cin>>n>>k;
for(int i=1;i<=k;i++){
scanf("%d",&p[i]);
mp[p[i]]++;
q_big.push(p[i]);
q_sml.push(p[i]);
}
sml[++cnt]=q_sml.top();
big[cnt]=q_big.top();
//v_s.push_back(q_sml.top());
//v_b.push_back(q_big.top());
//cout<<q_sml.top()<<' '<<q_big.top()<<endl;
for(int i=k+1;i<=n;i++){
scanf("%d",&p[i]);
mp[p[i-k]]--;
mp[p[i]]++;
q_sml.push(p[i]);
q_big.push(p[i]);
while(!q_sml.empty()&&mp[q_sml.top()]==0){
q_sml.pop();
}
while(!q_big.empty()&&mp[q_big.top()]==0){
q_big.pop();
}
sml[++cnt]=q_sml.top();
big[cnt]=q_big.top();
//v_s.push_back(q_sml.top());
//v_b.push_back(q_big.top());
//cout<<q_sml.top()<<' '<<q_big.top()<<endl;
}
for(int i=1;i<=cnt;i++){
printf("%d ",sml[i]);
}
cout<<endl;
for(int i=1;i<=cnt;i++){
printf("%d ",big[i]);
}
}map常数实在是太大了