1 条题解
-
0
本题是求解滑动窗口的,但是数据范围比较大,一定要离散化的,可以直接使用map来维护一个滑动窗口,时间复杂度是时间复杂度也是允许的
#include<cstdio> #include<iostream> #include<vector> #include<map> #include<cstring> #include<array> #include<queue> #include<algorithm> #include<set> #include<cmath> using namespace std; using i64=long long; //using i128=__int128; const i64 INF=1e18; const int mod=998244353; //const int N=1e9+7; void solve(){ int n,k; cin>>n>>k; vector<int>h(n+1); for(int i=1;i<=n;i++)cin>>h[i]; map<int,int>mp; //初始化map int ans=0; for(int i=1;i<=k;i++){ mp[h[i]]++; } ans=mp.size(); //进行窗口的滑动 for(int i=k+1;i<=n;i++){ mp[h[i-k]]--; if(mp[h[i-k]]==0)mp.erase(h[i-k]);//注意:这里要删除的是迭代器 mp[h[i]]++; ans=max(ans,(int)mp.size()); } cout<<ans<<'\n'; } int main(){ int _=1; //cin>>_; while(_--)solve(); return 0; }
- 1
信息
- ID
- 303
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 122
- 已通过
- 28
- 上传者