只考虑第一问，将珠子按照价值从小到大排序，设排序后第$i$小的为$b[i]$，定义二元组$(x,y)$表示当前珠子的总价值为$x$，用的价值最大的珠子为$y$，用一个小根堆来维护所有状态。一开始往堆中加入$(b[1],1)$状态，然后每次取出堆顶元素$(x,y)$，可以扩展出$(x+b[y+1],y+1)$以及$(x-b[y]+b[y+1],y+1)$两个状态。如此重复，直至取满$k$个。这部分的时间复杂度为$O(k\log k)$。

对于第二问，设第一问的答案为$limit$，然后按字典序进行爆搜，假设当前可以在$[l,n]$里选一个珠子加入，那么总和不能超过$limit$，可以通过若干次在线段树上二分找到所有这样的点。因为加上这个剪枝后，只会遍历到$k$个状态，所以这部分复杂度为$O(k\log n)$。

 

#include
     
      #include
      
       #include
       
        #include
        
         #define N 1000010using namespace std;typedef long long ll;typedef pair
         
           P;int n,k,i,a[N],b[N],ret,q[N],t,v[2100000];ll f[N];priority_queue
          
           
,greater
           
 >Q;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}void build(int x,int a,int b){ if(a==b){v[x]=::a[a];return;} int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b),v[x]=min(v[x<<1],v[x<<1|1]);}int ask(int x,int a,int b,int c,ll p){ if(c<=a){ if(v[x]>p)return 0; if(a==b)return a; } int mid=(a+b)>>1; if(c<=mid){ int t=ask(x<<1,a,mid,c,p); if(t)return t; } return ask(x<<1|1,mid+1,b,c,p);}void dfs(int x,ll s){ if(!ret)return; if(!s){ if(!(--ret))for(int i=1;i<=t;i++)printf("%d ",q[i]); return; } for(;x<=n;x++){ x=ask(1,1,n,x,s); if(!x)return; q[++t]=x; dfs(x+1,s-a[x]); t--; }}int main(){ read(n),read(k);k--; if(!k)return puts("0"),0; for(i=1;i<=n;i++)read(a[i]),b[i]=a[i]; sort(b+1,b+n+1); Q.push(P(b[1],1)); for(i=1;i<=k;i++){ P t=Q.top();Q.pop();f[i]=t.first; if(t.second==n)continue; Q.push(P(t.first+b[t.second+1],t.second+1)); Q.push(P(t.first-b[t.second]+b[t.second+1],t.second+1)); } printf("%lld\n",f[k]); for(i=k;f[i]==f[k];i--); ret=k-i; build(1,1,n); dfs(1,f[k]); return 0;}