【BZOJ4345】[POI2016]Korale

Description

有n个带标号的珠子，第i个珠子的价值为a[i]。现在你可以选择若干个珠子组成项链（也可以一个都不选），项链的价值为所有珠子的价值和。现在给所有可能的项链排序，先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序。请输出第k小的项链的价值，以及所用的珠子集合。

Input

第一行包含两个正整数n,k(1<=n<=1000000,1<=k<=min(2^n,1000000))。

第二行包含n个正整数，依次表示每个珠子的价值a[i](1<=a[i]<=10^9)。

Output

第一行输出第k小的项链的价值。

第二行按标号从小到大依次输出该项链里每个珠子的标号。

Sample Input

4 10
3 7 4 3

Sample Output

10
1 3 4

题解：求第k小我们自然想到超级钢琴那题，而枚举所有集合要用搜索，所以我们要模拟搜索的过程。

起初，我们将一个空集扔到小根堆中，然后每次取出堆顶元素，考虑DFS时，我们是从左到右枚举每个数，可能选也可能不选，那么我们模拟这个过程，分两种情况：

1.加入一个数，那么显然是加入右面最小的数。
2.将最后一个数换成一个数，那么显然是将当前数换成刚好比当前数大的那个数，这里采用超级钢琴的做法，维护当前数的选择区间[l,r]，假设当前数是x，那么在[l,x)和(x,r]中寻找新的最小数，替换当前数。

但是如何保证字典序最小呢？首先首位必须最小，那么我们将DFS的顺序反过来即可；然后记录一下每个状态是由哪个状态得到的，在取出一个状态的时候顺便记录一个这个状态的排名，比较时比较上一个状态的排名即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

using namespace std;

const int maxn=1000010;

typedef long long ll;

int n,m,N;

ll v[maxn];

int mx[21][maxn],Log[maxn];

struct node

{

	ll sum;

	int x,pre,l,r,rank;

}p[maxn*3];

struct number

{

	int a;

	number() {}

	number(int x) {a=x;}

	bool operator < (const number &c) const

	{

		int b=c.a;

		if(p[a].sum!=p[b].sum)	return p[a].sum>p[b].sum;

		if(p[a].x!=p[b].x)	return p[a].x>p[b].x;

		return p[p[a].pre].rank>p[p[b].pre].rank;

	}

};

priority_queue<number> q;

inline int MX(int a,int b)

{

	return ((v[a]==v[b])?(a<b):(v[a]<v[b]))?a:b;

}

inline int query(int a,int b)

{

	register int c=Log[b-a+1];

	return MX(mx[c][a],mx[c][b-(1<<c)+1]);

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void print(int x)

{

	if(!x)	return ;

	printf("%d ",p[x].x),print(p[x].pre);

}

int main()

{

	n=rd(),m=rd()-1;

	if(!m)

	{

		printf("0\n");

		return 0;

	}

	register int i,j,a,b,cnt;

	ll last=-1;

	for(i=1;i<=n;i++)	v[i]=rd(),mx[0][i]=i;

	for(i=2;i<=n;i++)	Log[i]=Log[i>>1]+1;

	for(j=1;(1<<j)<=n;j++)	for(i=1;i+(1<<j)-1<=n;i++)	mx[j][i]=MX(mx[j-1][i],mx[j-1][i+(1<<(j-1))]);

	N=1,p[1].x=query(1,n),p[1].sum=v[p[1].x],p[1].pre=0,p[1].l=1,p[1].r=n;

	q.push(number(1));

	while(m--)

	{

		i=q.top().a,q.pop();

		if(!m)

		{

			printf("%lld\n",p[i].sum),print(i);

			return 0;

		}

		if(p[i].sum>last)	last=p[i].sum,cnt=1;

		else	cnt++;

		p[i].rank=cnt;

		if(p[i].x!=1)

		{

			j=++N,p[j].pre=i,p[j].l=1,p[j].r=p[i].x-1,p[j].x=query(1,p[i].x-1),p[j].sum=p[i].sum+v[p[j].x];

			q.push(number(j));

		}

		a=(p[i].x>p[i].l)?query(p[i].l,p[i].x-1):0;

		b=(p[i].x<p[i].r)?query(p[i].x+1,p[i].r):0;

		if(a)

		{

			j=++N,p[j].pre=p[i].pre,p[j].x=a,p[j].l=p[i].l,p[j].r=p[i].x-1,p[j].sum=p[p[i].pre].sum+v[a];

			q.push(number(j));

		}

		if(b)

		{

			j=++N,p[j].pre=p[i].pre,p[j].x=b,p[j].l=p[i].x+1,p[j].r=p[i].r,p[j].sum=p[p[i].pre].sum+v[b];

			q.push(number(j));

		}

	}

}

巴特西

【BZOJ4345】[POI2016]Korale 堆（模拟搜索）