andyli

题解 CF1133D 【Zero Quantity Maximization】
根据题意得出当$c_i$为$0$时:$a_i\ne 0$时,$d=-\frac{b_i}{a_i}$$a_i = ...
扫描右侧二维码阅读全文
13
2019/08

题解 CF1133D 【Zero Quantity Maximization】

根据题意得出当$c_i$为$0$时:

  1. $a_i\ne 0$时,$d=-\frac{b_i}{a_i}$
  2. $a_i = b_i = 0$时,$d=0$

所以我们需要统计满足第2种情况的个数以及第1种情况中出现最多的$d$出现的次数。
判断$d$出现的个数可以用$map$来实现,首先用$gcd$约分,然后统一负号出现的位置,把这个分数出现的次数++,并同时计算$ans$,最后把满足第$2$种情况的个数与$ans$相加便是最终的答案。
代码如下:

#include <cstdio>
#include <map>
#include <numeric>
using namespace std;
const int maxn = 200005;

int A[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    int sum = 0, ans = 0;
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i++) {
        int a = A[i], b;
        scanf("%d", &b);
        if (!a && !b)
            sum++; // 第2种情况
        else if(!a) continue; // a=0时-b/0不合法
        else{
            if (1LL * a * b < 0) // 如果a, b异号,注意使用long long判断
                a = -abs(a), b = abs(b);
            else // a, b同号
                a = abs(a), b = abs(b);
            int t = gcd(a, b); // C++17中numeric头文件里包含gcd函数,不需要考虑正负
            ans = max(ans, ++mp[pair(b / t, a / t)]);
        }
    }
    printf("%d\n", sum + ans);
    return 0;
}
Last modification:November 6th, 2019 at 05:11 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment