又到吃饭时间，Polo面对饭堂里琳(fei)琅(chang)满(keng)目(die)的各种食品，又陷入了痛苦的抉择中：该是吃
手(jiao)打肉饼好呢，还是吃豆(cai)角(chong)肉片好呢？嗯……又不是天秤座怎么会酱紫呢？具体来说，一顿饭
由M个不同的部分组成(荤菜，素菜，汤，甜品，饮料等等)，Polo要在每个部分中选一种作为今天的午饭。俗话说
的好，永远没有免费的午餐，每种选择都需要有一定的花费。长者常常教导我们，便宜没好货，最便宜的选择估计
比较坑爹，可囊中羞涩的Polo还要把钱省下来给某人买生日礼物，这该怎么办呢？于是一个折中方案出来了：第K
便宜的组合要花多少钱？这就要靠你了。
Input
第一行两个数M，K，含义如上所述。
接下来M行，先是一个整数Ai，表示第i个部分有多少种选择。接下来用空格分开的Ai个整数表示每种选择的价格。
Ai>0， sigma(ai)<=500000，1<=M<=10，1<=K<=100000，1<=价格<=10^8。
Output
一行一个整数表示答案。
Sample Input
2 2
2 1 3
2 2 2
Sample Output
3
同上一篇Blog,可二分答案，可优先队列
#include<cstdio>
#include<algorithm>
#define maxm 12
#define maxn 500010
using namespace std;
char ch;
int m,k,a[maxm],val[maxm][maxn],min_val[maxm];
int l,r,mid,sum,tot;
inline bool isdigit(char ch){return ‘0‘<=ch&&ch<=‘9‘;}
inline void read(int &x){
for (ch=getchar();!isdigit(ch);ch=getchar());
for (x=0;isdigit(ch);x=x*10+ch-‘0‘,ch=getchar());
}
inline void check(int dep)
{
if (dep==m+1)
{
tot++;
return;
}
for (int i=1;i<=a[dep];i++)
if (sum+val[dep][i]+min_val[dep]<=mid)
{
//如果sum加上第dep第i列个元素，再加上今后可能取到的最小值是小于等于mid的话
sum+=val[dep][i];
check(dep+1);
if (tot==k) return;
sum-=val[dep][i];
}
else return;
}
int main(){
read(m),read(k);
for (int i=1;i<=m;i++)
{
read(a[i]);
for (int j=1;j<=a[i];j++) read(val[i][j]);
sort(val[i]+1,val[i]+a[i]+1);
r+=val[i][a[i]];
l+=val[i][1];
min_val[i-1]=val[i][1]; //取出每行最小值
}
for (int i=m-1;i>=1;i--)
min_val[i]+=min_val[i+1];
//min_val[i]代表针对每行的最小值，从第i+1行到最后一行，所取到的最小值
while (l!=r)
{
mid=(l+r)>>1;
sum=tot=0;
check(1);
if (tot==k) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
优先队列:
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<int> s;
int i,j,f[11][500001],a[100001],n,m,o[11];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&o[i]);
for(j=1;j<=o[i];j++)
scanf("%d",&f[i][j]);
sort(f[i]+1,f[i]+o[i]+1);
}
int now=min(m,o[1]);
for(i=1;i<=now;i++)a[i]=f[1][i];
for(i=2;i<=n;i++)
{
int maxx=123456789;
for(j=1;j<=o[i];j++)
for(int k=1;k<=now;k++)
{
if(a[k]+f[i][j]>maxx)break;
if(s.size()<m)
{
s.push(a[k]+f[i][j]);
if(s.size()==m)maxx=s.top();
}
else
if(a[k]+f[i][j]<maxx)
{
s.pop();
s.push(a[k]+f[i][j]);
maxx=s.top();
}
}
now=0;
while(!s.empty())
a[++now]=s.top(),s.pop();
for(j=1;j<=now/2;j++)
swap(a[j],a[now-j+1]);
}
printf("%d",a[m]);
}
这个题目还可以换种方法来描述：
有M+1个点，第i和第i+1个点之间有Ai条带权的有向边，求从1号点到M+1号点的第K短路是多少。
这个问题可以用经典的K短路算法来解决，具体我就不描述了，网上有很多资料。
在余鼎力《寻找第K优解的几种方法》中，还介绍了一种更快的方法，可以做到。
原文：https://www.cnblogs.com/cutemush/p/11679169.html