/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 4ms 2.566 MiB
#2 Accepted 3ms 2.691 MiB
#3 Accepted 2ms 2.699 MiB
#4 Accepted 352ms 4.191 MiB
#5 Accepted 202ms 2.441 MiB
#6 Accepted 179ms 3.574 MiB
#7 Accepted 216ms 3.312 MiB
#8 Accepted 244ms 3.32 MiB
#9 Accepted 241ms 3.574 MiB
#10 Accepted 217ms 3.441 MiB

代码

#include<bits/stdc++.h>
const int maxn=100001;
inline const void read(int &a)
{
	a=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
inline const void write(int a)
{
	if(a<0){a=-a;putchar('-');}
	if(a>9)write(a/10);
	putchar('0'+a%10);
}
inline const double max(double a,double b)
{
	if(a>b)return a;
	return b;
}
inline const double min(double a,double b)
{
	if(a<b)return a;
	return b;
}
inline const int lowbit(int a)
{
	return a&(-a);
}
int n,k,sum[maxn];
inline const void modify(int a,int b)
{
	a=a+1;
	while(a<=n)
	{
		sum[a]+=b;
		a+=lowbit(a);
	}
}
inline const int query(int a)
{
	a=a+1;
	int ans=0;
	while(a)
	{
		ans+=sum[a];
		a-=lowbit(a);
	}
	return ans;
}
double hash[maxn],num[maxn],size[maxn],beauty[maxn];
int order[maxn];
inline const bool comp(double a,double b)
{
	if(a<b)return true;
	return false;
}
inline const int find(double a)
{
	int l=1,r=n;
	while(l!=r)
	{
		int mid=(l+r)>>1;
		if(hash[mid]<a)l=mid+1;
		else r=mid;
	}
	while(l-1&&hash[l-1]==a)--l;
	return l;
}
inline const int solve(double mid)
{
	memset(sum,0,sizeof(sum));
	int ans=0;
	num[0]=0;
	for(int i=1;i<=n;i++)num[i]=hash[i]=num[i-1]+size[i]-mid*beauty[i];
	std::sort(hash+1,hash+1+n,comp);
	for(int i=1;i<=n;i++)
	{
		order[i]=find(num[i]);
		ans+=query(order[i]);
		if(num[i]>=0)ans++;
		modify(order[i],1);
	}
	return ans;
}
int main()
{
	double l=100000.0,r=-1.0;
	read(n);read(k);
	int t;
	for(int i=1;i<=n;i++){read(t);size[i]=double(t);}
	for(int i=1;i<=n;i++){read(t);beauty[i]=double(t);r=max(r,size[i]/beauty[i]);l=min(l,size[i]/beauty[i]);}
	while(r-l>=1e-3)
	{
		double mid=(r+l)/2;
		if(solve(mid)>=k)l=mid;
		else r=mid;
	}
	printf("%.2lf",(l+r)/2);
	return 0;
}

信息

递交者
类型
递交
题目
梁山伯与祝英台(原创)
题目数据
下载
语言
C++
递交时间
2017-10-24 11:38:26
评测时间
2017-10-24 14:49:26
评测机
分数
100
总耗时
1666ms
峰值内存
4.191 MiB