2019/10/22 test T1 题解

题目描述

给定n个a[i],b[i]，求min(x$\in$R){$\sum\limits_{i=1}^{n}$|a[i]*x+b[i]|}

输入格式

第 1行 1个整数 n
第 2行 n个整数，第 i个为 a[i],b[i]

输入格式

输出一行一个实数 y，表示答案。你可以输出任意位小数，随后系统会将你的输出与答案进行比较，只
有当你的输出与答案绝对误差不超过 $10^{-3}$ 时才能得到该测试点的分数

输入样例

2
1 1
2 -1

输出样例

1.50000000000

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define int long long

 #define maxn 300000+10

 #define INF 2147483647

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n;

 struct node

 {

     double a,b,val;

 }x[maxn];

 double minn=INF;

 inline bool cmp(node x,node y)

 {

     return x.val<y.val;

 }

 inline double cal(double num)

 {

     double ans=;

     for(int i=;i<=n;i++)

     {

         ans+=abs(x[i].a*num+x[i].b);

     }

     return ans;

 }

 signed main()

 {

     n=read();

     for(int i=;i<=n;i++)

     {

         scanf("%lf%lf",&x[i].a,&x[i].b);

         if(x[i].a==) continue;

         int re=x[i].b*-;

         x[i].val=double(re)/double(x[i].a);

     }

     if(n==)

     {

         write();

         return ;

     }

     sort(x+,x+n+,cmp);

     double l=x[].val,r=x[n].val;

     while(r-l>=1e-)

     {

         double m1=l+(r-l)/,m2=r-(r-l)/;

         if(cal(m1)<cal(m2)) r=m2;

         else l=m1;

     }

     printf("%.8f",cal(l));

     return ;

 }

巴特西

2019/10/22 test T1 题解

题目描述

输入格式

输入格式

输入样例

输出样例

最新文章

热门文章