D. Zero Quantity Maximization(hash+map)

题意:就是让c=a*x+b,给你一个a[],b[],让你尽可能多的让c[]=0,输出有多少。

思路:直接令c=0,则x=-b/a, 也就是一条直线,通过这样就用hash值使相同的k值映射到一起,使用了map<long double , int>,这样就直接映射了。

   让我吐血的是,这个还有特殊情况,a=0&&b=0, 注意b绝对不能在a不为0的情况下为0,至于为什么看原式。

#include<iostream>
#include<map>
using namespace std; #define ll long double map<ll, int>ss;
const long long mod = 1e17 + ;
const int maxn = 2e5+; int a[maxn], b[maxn];
int n, maxx; int gcd(int a, int b){ return b == ? a : gcd(b, a%b); }
int ans;
int main(){
cin >> n;
for (int i = ; i <= n; ++i)
{
cin >> a[i];
}
for (int i = ; i <= n; ++i)
cin >> b[i]; for (int i = ; i <= n; ++i){
if (a[i] == ){ ans += (b[i] == ); continue; }
int d = gcd(a[i], b[i]);
a[i] /= d; b[i] /= d;
ss[a[i] * 1.0 / b[i]]++;
} for (map<ll, int>::iterator it = ss.begin(); it != ss.end(); ++it){
if (it->second > maxx)maxx = it->second;
}
cout << maxx+ans << endl;
}
上一篇:Java核心技术卷一基础知识-第14章-多线程-读书笔记


下一篇:[Effective JavaScript 笔记]第63条:当心丢弃错误