D. Zero Quantity Maximization（CF： Codeforces Round #544 (Div. 3)）

墨蓝 2022-03-11 16:50 191阅读 0赞

### 题目描述： ###

You are given two arrays aa and bb, each contains nn integers.

You want to create a new array cc as follows: choose some real (i.e. not necessarily integer) number dd, and then for every i∈\[1,n\]i∈\[1,n\] let ci:=d⋅ai+bici:=d⋅ai+bi.

Your goal is to maximize the number of zeroes in array cc. What is the largest possible answer, if you choose dd optimally?

Input  
The first line contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of elements in both arrays.

The second line contains nn integers a1a1, a2a2, …, anan (−109≤ai≤109−109≤ai≤109).

The third line contains nn integers b1b1, b2b2, …, bnbn (−109≤bi≤109−109≤bi≤109).

Output  
Print one integer — the maximum number of zeroes in array cc, if you choose dd optimally.

###### 题目链接：[http://codeforces.com/contest/1133/problem/D][http_codeforces.com_contest_1133_problem_D] ######

题意：  
给出两个数组a,b;给出一个d（d可以为小数）。  
在定义一个数组c  
c\[i\]的元素等于d\*a\[i\]+b\[i\];  
请你找出一个d，使得，c\[i\]里面的元素为0的尽可能多。  
并输出最多为0的个数。  
分析：  
这道题是真的容易wa呀。  
这道题我是后来补的题，都wa了几次。  
思路的话，我是将每个位置的d算出来保存到c数组中。即 c\[i\]=-b\[i\] /a\[i\]；  
那么c\[i\]里面保存的就是满足a\[i\]和b\[i\]的对应d；  
最后找到最多的d就可以了。  
坑点：  
一开始wa5。wa5的话是出现0没有特判。  
例如：  
３  
０　２　６  
０　－２　８  
这个很明显当ｄ为１的时候。c数组中出现的0的次数最多。但是我一开始的时候，并没有考虑到这种情况。  
wa37，的话是精度问题，这个题用double的精度，还是太低了。必须要用long double 的类型才行。  
AC代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
       using namespace std;
    typedef long long ll;
    #define Se 10000000009
    #define INF 9999999999
    ll a[200001];
    ll b[200001];
    long double c[200001];
    int main()
    {
        ll n;
    
        while(~scanf("%I64d",&n))
        {
            ll cont=0;
            for(ll i=0;i<n;i++)
            {
                scanf("%I64d",&a[i]);
            }
            for(ll i=0;i<n;i++)
            {
                scanf("%I64d",&b[i]);
                if(a[i]==0&&b[i]==0)//如果都为0那么这个位置的d是随便什么值都可以的。
                                              //在这里置为Se，方便后面判断。
                {
                    c[i]=Se;cont++;//cont是统计有几个Se的。
                    continue;
                }
                if(b[i]==0)//如果就b[i]为0的话。那么a[i]和b[i]对应的d只能为0
                    {
                        c[i]=0;continue;
                    }
                else
                    {
                     if(a[i]==0)//如果就a[i]为0。那么对应位置上的d不伦为什么都不行。
                        {
                            c[i]=INF;continue;
                        }
                        c[i]=(long double)b[i]*(-1)/(double)a[i];//计算对应位置的d 
                        //printf("%.9lf\n",c[i]);
                    }
            }
            sort(c,c+n);//排序，方便查找出现次数最多的。
            ll maxx=0;
            ll cnt=1;
           /*for(ll i=0;i<n;i++)
                printf("%.5lf ",c[i]);
            printf("\n");*/
            for(ll i=1;i<n;i++)//查找出现次数最多的。
            {
                if(c[i]==c[i-1]&&c[i]!=INF&&c[i]!=Se)
                {
                    cnt++;continue;
                }
                maxx=max(maxx,cnt);
                cnt=1;
            }
            maxx=max(maxx,cnt);
            //这里是特判c[i]数组中会不会是全是不可能的数，和全是都可以的数。
            if((c[0]==c[n-1]&&c[0]==INF)||(c[0]==c[n-1]&&c[0]==Se))
                 maxx=0;
          printf("%I64d\n",maxx+cont);
        }
    }

[http_codeforces.com_contest_1133_problem_D]: http://codeforces.com/contest/1133/problem/D