对顶堆模板！！【DS对顶堆】ABC281 E - Least Elements

￡神魔★判官ぃ 2024-03-22 10:42 83阅读 0赞

**我想的思路和正解是差不多的**

**就是滑动窗口，每过去一个用DS维护一下前k个元素和sum**

**本来想的是用优先队列维护前k个**

**然后想着multiset维护前k个，但是具体不知道怎么操作**

**这里用的是multiset维护对顶堆**

**关于对顶堆，我在寒假的时候总结过**

**但是感觉没有这个帅，所以就顺便学一个这个，拿这个作为板子吧**

题意：

![116b18e8c221413095140334ad48b43c.png][]

思路：

考虑每过去一格，用DS维护前k个元素和sum

具体用什么DS呢，取决于我们需要维护什么

我们需要动态维护前k个元素和sum

因此选择对顶堆

每过去一格，删去a\[i\]，添加a\[i+m\]

具体怎么维护见代码：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    
    int pop_front(multiset<int> &s){
    	auto it=s.begin();
    	int val=*it;
    	s.erase(it);
    	return val;
    }
    
    int pop_back(multiset<int> &s){
    	auto it=prev(s.end());
    	int val=*it;
    	s.erase(it);
    	return val;
    }
    
    vector<int> v;
    multiset<int> l,r; 
    
    int n,m,k,sum=0;
    int a[mxn];
    
    void solve(){
    	cin>>n>>m>>k;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=1+m-1;i++){
    		sum+=a[i];
    		l.insert(a[i]);
    		if(l.size()>k){
    			int val=pop_back(l);
    			r.insert(val);
    			sum-=val;
    		}
    	}
    	for(int i=1;i+m-1<=n;i++){
    		v.push_back(sum);
    		if(k==m){
    			sum+=a[i+m]-a[i];
    		}else{
    			l.insert(a[i+m]);
    			sum+=a[i+m];
    			
    			int val=pop_back(l);
    			sum-=val;
    			r.insert(val);
    			
    			if(r.find(a[i])!=r.end()){
    				r.erase(r.find(a[i]));
    			}else{
    				l.erase(l.find(a[i]));
    				sum-=a[i];
    				int val=pop_front(r);
    				l.insert(val);
    				sum+=val;
    			}
    		}
    	}
    	for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[116b18e8c221413095140334ad48b43c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/004a94bf8cbc41629bc16c28280b4a39.png