/ Randle /

记录详情

Accepted

/in/foo.cc: In function 'int inc(int)':
/in/foo.cc:15:59: warning: no return statement in function returning non-void [-Wreturn-type]
 inline int inc(int x){while(x<(n+5)){c[x]++;x+=lowbit(x);}}
                                                           ^
# 状态 耗时 内存占用
#1 Accepted 5ms 2.375 MiB
#2 Accepted 5ms 2.715 MiB
#3 Accepted 5ms 4.355 MiB
#4 Accepted 166ms 4.848 MiB
#5 Accepted 98ms 4.738 MiB
#6 Accepted 110ms 4.852 MiB
#7 Accepted 124ms 3.875 MiB
#8 Accepted 126ms 3.5 MiB
#9 Accepted 126ms 4.848 MiB
#10 Accepted 126ms 4.598 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 int 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;
	}
	// 1 2 3 4 5 6 7 ```` (n+1)
	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:54:51
评测时间
2017-10-26 16:54:52
评测机
分数
100
总耗时
894ms
峰值内存
4.852 MiB