「JOJZ3855」选择困难症 - 宽搜+堆+k大查询 | Bill Yang's Blog

「JOJZ3855」选择困难症 - 宽搜+堆+k大查询

题目大意

    又到吃饭时间,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;
}
姥爷们赏瓶冰阔落吧~
0%