40pts奇怪问题求助
查看原帖
40pts奇怪问题求助
169594
Heart_Of_Iron_4楼主2024/9/12 20:43

为了测试我代码中的问题,我将我代码中的check改为一篇题解中的,但仍为40pts。但这题除了check也没啥东西啊?
原代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)/2.0)
double eps=0.0001,l,r,d[100100],e[100100],q[100100],p[100100];
int n,k,c[100100],a[100100],cnt;
bool cmp(double qwe,double wer)
{
	return qwe>wer;
}
int check(double v)
{
	cnt=0;
	for(int i=1;i<=n;++i)
	{
		d[i]=1.0*a[i]*c[i]-1.0*v*a[i];
		e[i]=-d[i];
		if(e[i]-d[i]<eps)cnt--;
	}
	//printf("%.4lf\n",v);
//	for(int i=1;i<=n;++i)printf("%lld ",d[i]);
//	puts("");
	sort(d+1,d+n+1,cmp);
	sort(e+1,e+n+1,cmp);
	for(int i=1,j=1;i<=n&&j<=n;++j)
	{
		while(d[i]-e[j]>eps&&i<=n)i++;
		cnt+=i-1;
	}
	return (cnt/2);
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&a[i],&c[i]);
	}
	l=0;
	r=1000000000.00;
	while(r-l>=eps)
	{
		if(check(mid)>k)l=mid;
		else r=mid;
	}
	printf("%.3lf",l);
	return 0;
}

改为题解中的check:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)/2.0)
double eps=0.0001,l,r,d[100100],e[100100],q[100100],p[100100];
int n,k,c[100100],a[100100],cnt;
bool cmp(double qwe,double wer)
{
	return qwe>wer;
}
/*int check(double v)
{
	cnt=0;
	for(int i=1;i<=n;++i)
	{
		d[i]=1.0*a[i]*c[i]-1.0*v*a[i];
		e[i]=-d[i];
		if(e[i]-d[i]<eps)cnt--;
	}
	//printf("%.4lf\n",v);
//	for(int i=1;i<=n;++i)printf("%lld ",d[i]);
//	puts("");
	sort(d+1,d+n+1,cmp);
	sort(e+1,e+n+1,cmp);
	for(int i=1,j=1;i<=n&&j<=n;++j)
	{
		while(d[i]-e[j]>eps&&i<=n)i++;
		cnt+=i-1;
	}
	return cnt/2;
}*/
int check(double v){
	int tot = 0;
	for(int i = 1;i <= n;i++){
		double x = a[i] * 1.0 * c[i],y = v * a[i]; 
		p[i] = x - y;
		q[i] = y - x; 
		if(q[i] - p[i] < eps) tot--;
	}
	sort(p + 1, p + n + 1, cmp);
	sort(q + 1, q + n + 1, cmp);
	int j = 0;
	for(int i = 1;i <= n;i++){
		while((q[j + 1] - p[i]) < eps && j + 1 <= n) j++;
		tot += j;
	}
	return (tot / 2 );
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&a[i],&c[i]);
	}
	l=0;
	r=1000000000.00;
	while(r-l>=eps)
	{
		if(check(mid)>k)l=mid;
		else r=mid;
	}
	printf("%.3lf",l);
	return 0;
}
2024/9/12 20:43
加载中...