举个例子：

对于这题来说，首先最优解肯定是选取所有种类中的最小值。

考虑 \(n=2\) 的情况怎么做。

把 \(a_{1,i}+a_{2,1}\) 全部加进堆里，然后对于一种 \(a_{1,i}+a_{2,p}\) 一种方案，如果选择了之后，就把 \(a_{1,i}+a_{2,p+1}\) 的方案加进堆里面。

这样我们可以在 \(O(n\log n)\) 的是将复杂度内解决这个情况。

现在考虑一般情况 \(n>2\) ，我们可以对于每种状态及 \(b_1,b_2\dots b_n\) 表示每个种类选到了哪里，然后选完一个方案之后，把 \(O(n)\) 的新方案加进我们的堆里面，但是这样是可能会导致一些重复的方案，不太好做，而且时间复杂度也是不正确的。

我们现在要满足的条件：

一种方案只能由一种方案拓展出来
且求出前 \(k\) 大后，\(k+1\) 定已被求出来。

设计一下状态进行转移：

将当前种类选取的 \(b_p\) 变成 \(b_{p+1}\)
选取下一种类，且把下一种类的 \(b_1\) 改选为 \(b_2\)
若当前种类选的是 \(b_2\) ，可以改回 \(b_1\) ，然后将下一种类变成 \(b_2\)

上面的转移已经满足了 \(1,3\) 条件，考虑如何满足 \(2\) 条件。

将所有种类按最大值减次大值从小到大排序，这样就可以满足 \(2\) 条件，根据贪心可知。

点击查看代码

#include<bits/stdc++.h>
#define int long long
typedef long long LL;

using namespace std;
const LL MAXN=3e5+10,inf=2e9;
const LL P=20190816170251;
LL n,m;
LL r[MAXN],p[MAXN];
LL vw[MAXN],s1,ans;
vector<int> v[MAXN];
bool cmp(LL x,LL y) {
	return x>y;
}
bool cmp1(LL x,LL y) {
	return vw[x]<vw[y];
}
struct ddl {
	LL w,id,p;
	friend bool operator <(ddl a,ddl b) {
		return a.w<b.w;
	} 
};
signed main () {
	freopen("contain.in","r",stdin);
	freopen("contain.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%lld",&r[i]);
		v[i].clear();
		for(int j=1;j<=r[i];++j) {
			int x;
			scanf("%lld",&x);
			v[i].push_back(x);
		}
		sort(v[i].begin(),v[i].end(),cmp);
		vw[i]=v[i][0]-v[i][1];
		s1+=v[i][0];
		if(r[i]==1) --i,--n;
	}
	for(int i=1;i<=n;++i) p[i]=i;
	sort(p+1,p+1+n,cmp1);
	priority_queue<ddl> q;
	LL ans=s1;
	q.push({s1-vw[p[1]],1,1});
	int cnt=1; --m;
	while(!q.empty()&&m) {
		ddl u=q.top();
		q.pop();
		ans=(ans*23333%P+u.w)%P;
		int i=u.id;
		if(u.p<r[p[i]]-1) {
			q.push({u.w-v[p[i]][u.p]+v[p[i]][u.p+1],i,u.p+1});
		}
		if(i<n) {
			q.push({u.w-vw[p[i+1]],i+1,1});
			if(u.p==1)
			q.push({u.w+vw[p[i]]-vw[p[i+1]],i+1,1});
		}
		--m;
	}
	printf("%lld\n",ans);
	return 0;
}

526互联

关于一类求前k优的题目

举个例子：