/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 8ms 4.477 MiB
#2 Accepted 10ms 3.852 MiB
#3 Accepted 7ms 4.863 MiB
#4 Accepted 103ms 5.375 MiB
#5 Accepted 80ms 4.469 MiB
#6 Accepted 96ms 4.98 MiB
#7 Accepted 111ms 4.5 MiB
#8 Accepted 114ms 4.848 MiB
#9 Accepted 115ms 5.25 MiB
#10 Accepted 108ms 5.117 MiB

代码

#include <bits/stdc++.h>
using namespace std;
int a[100001],b[100001];//原始数据 
double s[100001];//前序和 
struct node
{
	int p;
	double v;
	inline bool operator < (node x)
	{
		return v<x.v;
	}
}c[100001];//HASH
int HASH[100001];
int d[400001];//没错我就是树状数组!! 
inline int read()
{
	char ch=getchar();
	int x=0;
	while(!isdigit(ch))
		ch=getchar();
	while(isdigit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
int n,k;

inline int sum(int x)
{
	int ans=0;
	while(x)
	{
		ans+=d[x];
		x-=(x&-x); 
	}
	return ans;
}
inline void in(int x)
{
	while(x<=n)
	{
		d[x]++;
		x+=(x&-x);
	}
}
bool judge(double x)
{
	memset(d,0,sizeof(d));
	int i,ans=0;
	for(i=1;i<=n;i++)
	{
		s[i]=s[i-1]+(double)a[i]-(double)b[i]*x;
		c[i].p=i,c[i].v=s[i];
	}
	sort(c+1,c+n+1);//HASH,将数转化为整数; 
	for(i=1;i<=n;i++)
	{
		HASH[c[i].p]=i;
		if(c[i].v==c[i-1].v&&HASH[c[i-1].p]!=0)
			HASH[c[i].p]=HASH[c[i-1].p];
	}
	for(i=1;i<=n;i++)//树状数组闪亮登场!!!! 
	{
		ans+=sum(HASH[i]);
		in(HASH[i]+1);
		if(ans>=k)
			return true; 
	}
	return false;
}
int main()
{
	int i;
	double l=0,r=0,mid;
	n=read(),k=read();
	for(i=1;i<=n;i++)
		a[i]=read();
	for(i=1;i<=n;i++)
	{
		b[i]=read();
		r=max(r,(double)a[i]/b[i]);
	}
	while(l<r&&r-l>0.003)
	{
		mid=(l+r)/2;
		if(judge(mid)) l=mid;
		else r=mid;
	}
	printf("%.2lf",l);
}

信息

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