/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 4ms 756.0 KiB
#2 Accepted 6ms 2.371 MiB
#3 Accepted 5ms 2.375 MiB
#4 Accepted 157ms 4.125 MiB
#5 Accepted 93ms 3.5 MiB
#6 Accepted 107ms 3.344 MiB
#7 Accepted 120ms 3.453 MiB
#8 Accepted 123ms 3.5 MiB
#9 Accepted 122ms 3.359 MiB
#10 Accepted 123ms 3.328 MiB

代码

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 100005
using namespace std;
int a[maxn],b[maxn];
int n,k;
double s[maxn];
int t2[maxn];
int  c[maxn];
inline int lowbit(int x) { return x&(-x);}
inline int sum(int x){int ret = 0;while(x>0){ret+=c[x];x-=lowbit(x);}return ret;}
inline void inc(int x){while(x<(n+5)){c[x]++;x+=lowbit(x);}}
struct pp{int pos;double val;}pps[maxn];
bool operator<(pp &p1,pp &p2){
	return p1.val<p2.val;
}
int check(double p){
	memset(c,0,sizeof(c));
	for(int i = 1;i<=n;i++)	s[i+1] = s[i]+(1.0*a[i]-1.0*p*b[i]);
	for(int i = 1;i<=n+1;i++){pps[i].val  = s[i];pps[i].pos = i;}
	sort(pps+1,pps+2+n);
	for(int i = 1;i<=n+1;i++)t2[pps[i].pos] = i;
	int aans = 0;
	for(int i = 1;i<=n+1;i++){aans+=sum(t2[i]);inc(t2[i]);}
	return aans;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i = 1;i<=n;i++) scanf("%d",a+i);
	for(int i = 1;i<=n;i++) scanf("%d",b+i);
	double l = 0, r= 0;
	for(int i = 1;i<=n;i++) r= max(r,1.0*a[i]/b[i]);
	while(l<r&&r-l>0.003){
		double mid = (l+r)/2.0;
		int ck = check(mid);
		if(ck>=k)l = mid;else r = mid;
	}
	printf("%.2f",l);
	return 0;
}

信息

递交者
类型
递交
题目
梁山伯与祝英台(原创)
题目数据
下载
语言
C++
递交时间
2017-10-26 17:05:23
评测时间
2017-10-26 17:05:23
评测机
分数
100
总耗时
864ms
峰值内存
4.125 MiB