/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 5ms 4.32 MiB
#2 Accepted 3ms 708.0 KiB
#3 Accepted 2ms 720.0 KiB
#4 Accepted 135ms 4.941 MiB
#5 Accepted 104ms 3.691 MiB
#6 Accepted 106ms 3.699 MiB
#7 Accepted 93ms 2.82 MiB
#8 Accepted 115ms 4.816 MiB
#9 Accepted 97ms 4.703 MiB
#10 Accepted 119ms 2.816 MiB

代码

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 100005
using namespace std;
int a[maxn],b[maxn];
double t[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);
	for(int i = 1;i<=n;i++) t[i] = 1.0*a[i]/b[i];
	sort(t+1,t+n+1);
	double ans = t[n];
	double l = 0,r = ans;
	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 16:57:22
评测时间
2017-10-26 16:57:22
评测机
分数
100
总耗时
784ms
峰值内存
4.941 MiB