首页 技术 正文
技术 2022年11月23日
0 收藏 514 点赞 3,810 浏览 1899 个字

题目:

Description

【问题描述】

从n个数中选若干(至少1)个数求和,求所有方案中第k小的和(和相同但取法不同的视为不同方案)。
【输入格式】
    第一行输入2个正整数n,k。
    第二行输入这n个正整数。
【输出格式】
    输出第k小的和。
【样例输入】
5 12
1 2 3 5 8
【样例输出】
8
【样例解释】
    前12小的和分别为:1 2 3 3 4 5 5 6 6 7 8 8
【数据规模和约定】
    测试点1,n<=16。
    测试点2-3,n<=100,k<=500。
    测试点4-5,n<=1000,k<=5000。
    测试点6-8,n<=10^5,k<=5*10^5。
    测试点9-10,n<=35。
    对于所有数据,1<=k<2^n,n个正整数每个都不超过10^9。


题解:

  80%数据:用二元组(sum,i)表示和为sum,当前考虑第i个位置是否要选,以sum+a[i]为权值维护。每次扩展到(sum+a[i],i)和(sum,i+1)。时间复杂度O(KlogK)剩下20%数据:二分答案以后折半搜索,时间复杂度O(2^{K/2}logW)

心得:

  优先队列是个好东西,折半搜索是个好东西;

代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cctype>
#include<queue>
using namespace std;
const int N=;
const int M=1e7+;
struct node
{
long long sum;
int pos;
node(long long sum,int pos):sum(sum),pos(pos){}
};
inline bool operator < (const node &a,const node &b)
{
return a.sum>b.sum;
}
priority_queue<node>que;
long long num[N];
long long vala[M],valb[M];
long long k;
int tota=,totb=;
int n;
void solve1()
{
que.push(node(num[],));
for(int i=;i<k;i++)
{
long long tsum=que.top().sum;
int tpos=que.top().pos;
que.pop();
if(tpos<=n)
{
que.push(node(tsum-num[tpos-]+num[tpos],tpos+));
que.push(node(tsum+num[tpos],tpos+));
}
}
printf("%lld\n",que.top().sum);
}
void dfs1(int u,int des,long long val)
{
if(u>des)
{
if(val)
vala[++tota]=val;
}
else
{
dfs1(u+,des,val+num[u]);
dfs1(u+,des,val);
}
}
void dfs2(int u,int des,long long val)
{
if(u>des)
if(val)
valb[++totb]=val;
else
{
dfs2(u+,des,val+num[u]);
dfs2(u+,des,val);
}
}
bool jud(long long val)
{
long long temp=;
int j=;
for(int i=tota;i>=;i--)
{
if(vala[i]>val) continue;
for(;j<=totb&&vala[i]+valb[j]<=val;j++);
temp+=j;
}
return temp>k;
}
void solve2()
{
dfs1(,n/,);
dfs2(n/+,n,);
sort(vala+,vala+tota+);
sort(valb+,valb+totb+);
long long l=,r=0x3f3f3f3f3f3f3f3f;
while(l<=r)
{
long long mid=(l+r)/;
if(jud(mid)) r=mid-;
else l=mid+;
}
printf("%lld\n",r+);
}
int main()
{
scanf("%d%lld",&n,&k);
for(int i=;i<=n;i++)
scanf("%lld",&num[i]);
sort(num+,num+n+);
long long j=0x3f3f3f3f3f3f3f3f;
if(n>) solve1();
else solve2();
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/140743.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站