为了测试我代码中的问题,我将我代码中的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;
}