P5967 [POI 2016] Korale 题解

P5967 [POI 2016] Korale

题目描述

有 $n$ 个带标号的珠子，第 $i$ 个珠子的价值为 $a_i$。

现在你可以选择若干个珠子组成项链（也可以一个都不选），项链的价值为所有珠子的价值和。

给出所有可能的项链排序，先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序。

请输出第 $k$ 小的项链的价值，以及所用的珠子集合。

输入格式

第一行包含两个正整数 $n,k$。
第二行包含 $n$ 个正整数，依次表示每个珠子的价值 $a_i$。

输出格式

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

输入输出样例 #1

输入 #1

4 10
3 7 4 3

输出 #1

10
1 3 4

说明/提示

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le k\le \min (2^n,10^6)$，$1\le a_i\le 10^9$。

思路

类似P2048超级钢琴~

把两问分开做。

第一问。先将数从小到大排序。然后维护一个优先队列，队列元素为 $(w,i)$ 表示此时价值为 $w$ ,并且选到了第 $i$ 个，队列中按价值排序。每次我们取出一个最小价值，出队同时判断答案，然后再加入 $(w+a_{i+1},i+1)$ 表示选择 $i+1$ ，加入$(w+a_{i+1}-a_i,i+1)$ ，表示反悔这一步的操作。

第二问。可以根据第一问的答案来暴搜。也就是要找答案为 $ans$,小于等于$ans$ 的数有 $k$ 个的方案。从前往后搜来保证字典序最小。直接 $O(n)$ 找可行状态复杂度爆炸，我们用线段树记录最小值。每次线段树上二分确定位置(每次找字典序最小且符合条件的点）。每次二分是 $O(\text{l}ogn)$ ,至多进行 $O(k)$ 次，所以复杂度是$O(klogn)$

code:

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+15;
ll n,k;
ll a[N],b[N],ans2[N];	
ll lst=0,cnt=0,nw=0;
struct tree{
	int l,r;
	ll w,mn;
}tr[N<<2]; 
struct node{
	ll w,len;
	bool operator < (const node &p) const{
		return w>p.w;
	}
};
priority_queue<node> q;
ll read(){
	ll x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x;
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].mn=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tr[p].mn=min(tr[p<<1].mn,tr[p<<1|1].mn);
}
int query(int p,int l,int r,int k,ll x){
	if(k<=l){
		if(tr[p].mn>x) return 0;
		if(l==r) return l;
	}
	int mid=(l+r)>>1;
	if(k<=mid){
		int y=query(p<<1,l,mid,k,x);
		if(y) 
		return y;
	}//else{
		return query(p<<1|1,mid+1,r,k,x);
//	}
}
void dfs(int nwi,ll as){
//	cout<<nw<<" "<<as<<" "<<cnt<<endl;
	if(as==0){
		cnt--;
		if(cnt!=0) return ;
		for(int i=1;i<=nw;++i){
			printf("%lld ",ans2[i]);
		}
		printf("\n");
		return ;
	}
	if(cnt<0) return ;
	for(int i=nwi+1;i<=n;++i){
		i=query(1,1,n,i,as);//i右侧第一个<as 
		if(i==0) return ;
		ans2[++nw]=i;
		dfs(i,as-a[i]);
		nw--;
	}
}
int main(){
	//freopen("pearl.in","r",stdin);
	//freopen("pearl.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	k--;
	for(int i=1;i<=n;++i){
		a[i]=read();
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	build(1,1,n);
	node xx;
	xx.w=b[1],xx.len=1;
	q.push(xx);
	cnt=0;
	for(int i=1;i<=k;++i){
		node x=q.top();
		q.pop();
		if(x.w==lst) cnt++;
		else lst=x.w,cnt=1;
		x.len++;
		if(x.len>n) continue;
		x.w+=b[x.len];
		q.push(x);
		x.w-=b[x.len-1];
		q.push(x);
	}
//	cout<<cnt<<endl;
	printf("%lld\n",lst);
	dfs(0,lst);
	return 0;
}