标签：线段树，dfs，堆
题目
Description
有n个带标号的珠子，第i个珠子的价值为a[i]。现在你可以选择若干个珠子组成项链（也可以一个都不选），项链的价值为所有珠子的价值和。
现在给所有可能的项链排序，先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序。
请输出第k小的项链的价值，以及所用的珠子集合。
Input
第一行包含两个正整数\(n,k(1\leq n\leq 1000000,1\leq k\leq min(2^n,1000000))\)。
第二行包含n个正整数，依次表示每个珠子的价值\(a[i](1\leq a[i]\leq 10^9)\)。
Output
第一行输出第k小的项链的价值。
第二行按标号从小到大依次输出该项链里每个珠子的标号。
Sample Input
4 10
3 7 4 3
Sample Output
10
1 3 4
分析
每一条项链可以用一个二元组\((i,j)\)表示权值为i，最大的为j号（从小到大排序之后）
那么把这个二元组放进堆中，\((i,j)\)可以拓展到\((i-a[j]+a[j+1],j+1)\)或者\((i+a[j+1],j+1)\)，然后一直拓展到k个为止
因为每次转移，新的状态和肯定只会比之前的大或相等，所以我们从\((a[1],1)\)开始转移\(k-1\)次一定能得到第k小的价值，复杂度\(O(k \log k)\)
难点在于如何寻找方案
我们可以直接dfs，得到第k小，那么只要保证只搜索\(1->k\)中的状态即可
那么可以用线段树得到\((i,n)\)中比t小的最前面的元素，那么每次就不需要循环n个，这样保证只搜索到k个
总的时间复杂度为\(O(k \log n)\)
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
#define mid ((l+r)>>1)
#define lson p<<1
#define rson p<<1|1
const int maxn=1e6+6;
int n,m,cnt,top,a[maxn],num[maxn],val[maxn<<2],stk[maxn];ll ans[maxn];
struct node{ll val;int id;};
priority_queue<node> q;
inline bool operator < (node a,node b){return a.val>b.val;}
void build(int p,int l,int r){
if(l==r){val[p]=a[l];return;}
build(lson,l,mid);build(rson,mid+1,r);
val[p]=min(val[lson],val[rson]);
}
inline int query(int p,int l,int r,int Q,ll y){
if(Q<=l){
if(val[p]>y)return 0;
if(l==r)return l;
}
if(Q<=mid){
int t=query(lson,l,mid,Q,y);
if(t)return t;
}
return query(rson,mid+1,r,Q,y);
}
void dfs(int k,ll rst){
if(!cnt)return;int i;
if(!rst){
cnt--;
if(!cnt)for(i=1;i<=top;i++)printf("%d ",stk[i]);
return;
}
for(i=k+1;i<=n;i++){
i=query(1,1,n,i,rst);
if(i){
stk[++top]=i;dfs(i,rst-a[i]);top--;
}else break;
}
}
int main()
{
n=read(),m=read()-1;
if(!m){puts("0");return 0;}
rep(i,1,n)a[i]=num[i]=read();
sort(num+1,num+1+n);
node u={num[1],1};q.push(u);
rep(i,1,m){
node now=q.top();q.pop();ans[i]=now.val;
if(i<m&&now.id<n){
now.id++;now.val+=num[now.id];q.push(now);
now.val-=num[now.id-1];q.push(now);
}
}
for(int i=m;i&&ans[i]==ans[m];i--)cnt++;
printf("%lld\n",ans[m]);
build(1,1,n);dfs(0,ans[m]);
return 0;
}
