梁山伯与祝英台(原创)
注意:因无spj,如果因为精度问题不能得到满分,请与管理员联系。但正常做法应该没问题。
【题目描述】
《梁山伯与祝英台》是中国古代民间四大爱情故事之一,自东晋始,在民间流传已有一千七百多年,可谓中国家喻户晓,流传深远,被誉为爱情的千古绝唱。
话说从前,梁山伯与祝英台在最初见面时,有一天在院中戏耍。祝英台对梁山伯说:“我们来玩个很高级的游戏吧!”梁山伯一听,自然欣喜无比。游戏规则是这样的:祝英台给梁山伯一群排成一排的n只蝴蝶,每一只蝴蝶都有两个指数大小sizei和美丽值beautyi。当蝴蝶很大的时候,看起来像飞蛾,于是祝英台感到了恶心;当蝴蝶很美的时候,看起来如翩翩起舞的仙女,祝英台感到了快乐。梁山伯每次只能选定一个区间[l,r],于是得到一个sumsize[l,r]:区间sumi之和, 和sumbeauty[l,r] :区间beautyi之和,然后区间值mark[l,r]=sumsize[l,r]/sumbeauty[l,r]。祝英台想知道,在所有的(n+1)*n/2个区间中,第k大的那个区间值mark[l,r]是多少。
祝英台如是说:“梁山伯,你如果能解出来,我就告诉你我其实是女生的秘密哦!”,梁山伯想:“他到底要告诉我什么秘密呢?”
【输入格式】
第一行n,k,表示一共有n只小蝴蝶,第k大的区间值。
接下来n个数,为sizei。
接下来n个数 ,为beautyi。
【输出格式】
一个保留两位小数ans,表示第k大的mark[l,r]。
【输入样例】
4 2
3 5 2 3
2 3 1 2
【输出样例】
1.75
【样例说明】
mark[1,1]=1.50,mark[2,2]=1.67,mark[3,3]=2.00,mark[4,4]=1.50,mark[1,2]=1.60,mark[2,3]=1.75
,mark[3,4]=1.67,mark[1,3]=1.67,mark[2,4]=1.67,mark[1,4]=1.62。第二大的mark是1.75
【数据规模】
对于30%的数据n<=1e3
对于额外的20%的数据n<=1e5,k==1
对于100%的数据n<=1e5
1<=beautyi,sizei<=1e5,保证数据随机
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 15
- 已通过
- 3
- 通过率
- 20%
- 上传者