4 条题解

  • 2
    @ 2026-10-21 9:05:11

    这里有一个无需单调队列 DP 与线段树的做法,仅需优先队列。具体思路见注释

    
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+5;
    int n,m,a[N],sum;
    struct node{
    	int sum;//当前的和 
    	int id;//上一个取的位置 
    };
    priority_queue<node> pq;//优先队列 
    node makenode(int x,int y){//数字转结构体 
    	node aa;
    	aa.sum=x; aa.id=y;
    	return aa;
    }
    bool operator < (node a,node b){//优先队列需要重载运算符 < 
    	return a.sum>b.sum;//先与总和小的尝试匹配 
    }
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
    //	考虑转化,取若干个数,每隔最多 m 个数必须选一个数
    //	求其和的最小值,最后用总和减去它 
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		sum+=a[i];//总和 
    	}
    	pq.push(makenode(0,0));//初始化 (选了总和为 0 的数,在位置 0)  
    	for(int i=1;i<=n;i++){
    		node x=pq.top();//由于可能重复匹配,因此先不弹出 
    		while(i-x.id>m+1){//优先队列的懒惰删除 
    		//由于第 i 位无法匹配的 i+? 也无法匹配,因此直接删除 
    			pq.pop();
    			x=pq.top();
    		}
    		pq.push(makenode(a[i]+x.sum,i));//将选 i 的情况加入队列 
    		//由于我们用最优情况去匹配,因此仅需将这种情况入队即可 
    	}
    	node x=pq.top();
    	while(n-x.id>m){//找到最优结果 
    		pq.pop();
    		x=pq.top();
    	}
    	cout<<sum-x.sum;//总和 - 最小的不选的和 = 答案 
    	return 0;
    }
    

    时间复杂度 O(Nlog⁡N)O(N\log N),但比线段树常数小,空间复杂度 O(N)O(N)

    AC记录

信息

ID
329
时间
1000ms
内存
256MiB
难度
8
标签
(无)
递交数
135
已通过
23
上传者