网站建设新闻发布注意,用js做简单的网站页面,江苏省句容建设局网站,c2c客户有哪些下单入口P5967 [POI 2016] Korale
题目描述
有 nnn 个带标号的珠子#xff0c;第 iii 个珠子的价值为 aia_iai。
现在你可以选择若干个珠子组成项链#xff08;也可以一个都不选#xff09;#xff0c;项链的价值为所有珠子的价值和。
给出所有可能的项链排序#xff0c;先按…P5967 [POI 2016] Korale
题目描述
有 nnn 个带标号的珠子第 iii 个珠子的价值为 aia_iai。
现在你可以选择若干个珠子组成项链也可以一个都不选项链的价值为所有珠子的价值和。
给出所有可能的项链排序先按权值从小到大排序对于权值相同的根据所用珠子集合的标号的字典序从小到大排序。
请输出第 kkk 小的项链的价值以及所用的珠子集合。
输入格式
第一行包含两个正整数 n,kn,kn,k。 第二行包含 nnn 个正整数依次表示每个珠子的价值 aia_iai。
输出格式
第一行输出第 kkk 小的项链的价值。 第二行按标号从小到大依次输出该项链里每个珠子的标号。
输入输出样例 #1
输入 #1
4 10
3 7 4 3输出 #1
10
1 3 4说明/提示
对于 100%100\%100% 的数据1≤n≤1061\le n\le 10^61≤n≤1061≤k≤min(2n,106)1\le k\le \min(2^n,10^6)1≤k≤min(2n,106)1≤ai≤1091\le a_i\le 10^91≤ai≤109。
思路
类似P2048超级钢琴~
把两问分开做。
第一问。先将数从小到大排序。然后维护一个优先队列队列元素为 (w,i)(w,i)(w,i) 表示此时价值为 www ,并且选到了第 iii 个队列中按价值排序。每次我们取出一个最小价值出队同时判断答案然后再加入 (wai1,i1)(wa_{i1},i1)(wai1,i1) 表示选择 i1i1i1 加入(wai1−ai,i1)(wa_{i1}-a_i,i1)(wai1−ai,i1) 表示反悔这一步的操作。
第二问。可以根据第一问的答案来暴搜。也就是要找答案为 ansansans,小于等于ansansans 的数有 kkk 个的方案。从前往后搜来保证字典序最小。直接 O(n)O(n)O(n) 找可行状态复杂度爆炸我们用线段树记录最小值。每次线段树上二分确定位置(每次找字典序最小且符合条件的点。每次二分是 O(logn)O(\text log n)O(logn) ,至多进行 O(k)O(k)O(k) 次所以复杂度是O(klogn)O(klogn)O(klogn)
code: cpp
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e615;
ll n,k;
ll a[N],b[N],ans2[N];
ll lst0,cnt0,nw0;
struct tree{int l,r;ll w,mn;
}tr[N2];
struct node{ll w,len;bool operator (const node p) const{return wp.w;}
};
priority_queuenode q;
ll read(){ll x0;char cgetchar();while(c0||c9){cgetchar();}while(c0c9){x(x1)(x3)(c^48);cgetchar();}return x;
}
void build(int p,int l,int r){tr[p].ll,tr[p].rr;if(lr){tr[p].mna[l];return ;}int mid(lr)1;build(p1,l,mid);build(p1|1,mid1,r);tr[p].mnmin(tr[p1].mn,tr[p1|1].mn);
}
int query(int p,int l,int r,int k,ll x){if(kl){if(tr[p].mnx) return 0;if(lr) return l;}int mid(lr)1;if(kmid){int yquery(p1,l,mid,k,x);if(y) return y;}//else{return query(p1|1,mid1,r,k,x);
// }
}
void dfs(int nwi,ll as){
// coutnw as cntendl;if(as0){cnt--;if(cnt!0) return ;for(int i1;inw;i){printf(%lld ,ans2[i]);}printf(\n);return ;}if(cnt0) return ;for(int inwi1;in;i){iquery(1,1,n,i,as);//i右侧第一个as if(i0) 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 i1;in;i){a[i]read();b[i]a[i];}sort(b1,b1n);build(1,1,n);node xx;xx.wb[1],xx.len1;q.push(xx);cnt0;for(int i1;ik;i){node xq.top();q.pop();if(x.wlst) cnt;else lstx.w,cnt1;x.len;if(x.lenn) continue;x.wb[x.len];q.push(x);x.w-b[x.len-1];q.push(x);}
// coutcntendl;printf(%lld\n,lst);dfs(0,lst);return 0;
}
