单调队列，滑动窗口
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; vector<int>a(n); int k; cin>>k; for(int i=0;i<n;i++) { cin>>a[i]; } deque<int>q; vector<int>ans; ==最大值== for(int i=0;i<n;i++) { while(!q.empty()&&q.front()+k<=i) { q.pop_front(); }//判断此时的滑动窗口是否已满，满的话执行，去掉队首 while(!q.empty()&&a[q.back()]<=a[i]) { q.pop_back(); }//在找最大值的时候，有比a[i]要小的元素，因此不能让它留在队首，要去掉 q.push_back(i);//让新的下标进入队列 if(i>=k-1)ans.push_back(a[q.front()]);//在达到滑动窗口的大小后，都会判出一个最大值 } vector<int>cnt; deque<int>q_min; 最小值 for(int i=0;i<n;i++) { while(!q_min.empty()&&q_min.front()+k<=i) { q_min.pop_front(); } while(!q_min.empty()&&a[q_min.back()]>=a[i]) { q_min.pop_back(); } q_min.push_back(i); if(i>=k-1)cnt.push_back(a[q_min.front()]); } for(int x:cnt) { cout<<x<<" "; } cout<<endl; for(int y:ans) { cout<<y<<" "; } }题目大意：在不超过m的滑动窗口中，找到最大和
#include<bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } // 1. 计算前缀和 vector<int> s(n + 1, 0); for (int i = 1; i <= n; ++i) { s[i] = s[i - 1] + a[i]; } deque<int>q; int ans=-1e18; for(int i=0;i<n;i++) { while(!q.empty()&&q.front()+m<i) { q.pop_front(); }//判断滑动窗口是否满了，满的话出队 if(!q.empty()) ans=max(ans,s[i]-s[q.front()]);//留下每一次滑动窗口下最大的和 while(!q.empty()&&s[q.back()]>=s[i]) q.pop_back();//如果该下标下的前缀和大于后者的前缀和，这把这个下标除去，因为减的越大，留下的越小，要留下较大的 q.push_back(i);//下标入队 } cout<<ans<<endl; }题目大意：在出现的所有时间下，算时间差在86400内不同国家的个数
#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define pii pair<int,int> #define fi first #define se second const int N=101; void slove(){ int n; cin>>n; queue<pair<int,vector<int>>>q; vector<int>cnt(100005,0); int ans=0; for(int i=0;i<n;i++) { int t,k; cin>>t>>k; vector<int>s(k); for(int i=0;i<k;i++) { cin>>s[i]; } //把不在这个时间差的国家从不同国家数中除去 while(!q.empty()&&q.front().first<=t-86400) { auto& ship=q.front(); for(int country:ship.second) { cnt[country]--; if(cnt[country]==0) { ans--; } } q.pop(); } //记录不同国家数 for(int country:s) { if(cnt[country]==0) ans++; cnt[country]++; } q.push({t,s}); cout<<ans<<endl; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _=1; //cin>>_; while(_--) slove(); return 0; }