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;
}