首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round #544 (Div. 3) D. Zero Quantity Maximization(思维)

Codeforces Round #544 (Div. 3) D. Zero Quantity Maximization(思维)

作者头像
Ch_Zaqdt
发布2019-03-15 11:02:14
3440
发布2019-03-15 11:02:14
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

题目链接:http://codeforces.com/contest/1133/problem/D

       题意是输入一个n,加下来分别输入n个a[i]和b[i],现在让你找一个d,现在要求一个c数组,c[i] = d * a[i] + b[i],要使的c数组中有最多的0,问最多的0的个数为多少

       思路就是对a[i]/b[i]化成最简分数,求一个最多的出现的分数的个数就好了。需要注意的是a[i]和b[i]都为0和a[i]为0的情况,这个我就不详细的讲了,自己结合上面的式子想一下吧


AC代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int a[200005], b[200005];
typedef pair<int,int> p;

int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(int i=0;i<n;i++){
    scanf("%d",&b[i]);
  }
  map<pair<int,int>,int> ma;
  int x = 0;
  int ans = 0;
  for(int i=0;i<n;i++){
    int xx = a[i];
    int yy = b[i];
    if(xx == 0 && yy == 0){
      x ++;
      continue;
    }
    if(xx == 0){
      continue;
    }
    ll zz = __gcd(xx, yy);
    xx /= zz;
    yy /= zz;
    ma[p(xx, yy)] ++;
    ans = max(ans, ma[p(xx, yy)]);
  }
  printf("%d\n", ans + x);
  return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019年03月08日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档