题目大意
又到吃饭时间，Polo面对饭堂里琳(fei)琅(chang)满(keng)目(die)的各种食品，又陷入了痛苦的抉择中：该是吃手(jiao)打肉饼好呢，还是吃豆(cai)角(chong)肉片好呢？嗯……又不是天秤座怎么会酱紫呢？
具体来说，一顿饭由$M$个不同的部分组成(荤菜，素菜，汤，甜品，饮料等等)，Polo要在每个部分中选一种作为今天的午饭。
俗话说的好，永远没有免费的午餐，每种选择都需要有一定的花费。长者常常教导我们，便宜没好货，最便宜的选择估计比较坑爹，可囊中羞涩的Polo还要把钱省下来给某人买生日礼物，这该怎么办呢？
于是一个折中方案出来了：第$K$便宜的组合要花多少钱？这就要靠你了。
题目分析
又是$K$小问题，$K$小问题我还没见过不用堆维护的。
不难想到暴力算法：搜索出所有可能情况，将其放入堆中取出$K$小。
但是状态量太大，复杂度难以接受。
考虑优化该暴力算法：若以固定顺序加入状态，并保证该顺序能够依次取到最优解，并保证每次加入的状态量不大，最后即可快速的求得$K$小。（其实这就是$A^*$求$K$短路的思想）
因此我们可以先从最小的状态往后扩展，不妨规定从上往下从左往右更换选择。
对于当前状态$S$有两种选择：
- 当前状态继续向右扩展
- 当前状态跳到下面的某一行从起始开始扩展
这样就可以以最优的顺序遍历完$K$小了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
struct Point {
int x,pos;
LL v;
bool operator < (const Point& b) const {
return v>b.v;
}
} st;
priority_queue<Point>Q;
int m,k,Len[15];
vector<int>a[15];
int main() {
m=Get_Int();
k=Get_Int();
for(int i=1; i<=m; i++) {
int len=Get_Int();
Len[i]=len;
for(int j=1; j<=len; j++)a[i].push_back(Get_Int());
sort(a[i].begin(),a[i].end());
st.v+=a[i][0];
}
st.x=1,st.pos=0;
Q.push(st);
for(int Rank=1; Rank<k; Rank++) {
Point Now=Q.top();
Q.pop();
if(Now.pos+1<Len[Now.x]) {
Point Next=Now;
Next.v-=a[Now.x][Now.pos];
Next.v+=a[Now.x][Now.pos+1];
Next.pos++;
Q.push(Next);
}
for(int i=Now.x+1; i<=m; i++) {
Point Next=Now;
Next.x=i;
Next.pos=1;
Next.v+=a[i][1]-a[i][0];
Q.push(Next);
}
}
printf("%lld\n",Q.top().v);
return 0;
}
|
