https://codeforces.com/contest/1133/problem/D

題解：就是求斜率相同的最大個數

特判a[i]? b[i]為0的時候三種情況，其中a[i]? b[i]同時為0時的情況可以加到答案里

C++版本一

long double 有精度問題

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=200000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans,cnt,flag,temp,sum; int a[N]; int b[N]; long double c[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&b[i]);}for(int i=1;i<=n;i++){if(a[i]==0){if(b[i]!=0)c[i]=-INF;else{cnt++;c[i]=INF;}continue;}c[i]=(long double)b[i]/(long double)a[i];}sort(c+1,c+n+1);for(int i=1;i<=n;i++){if(c[i]==-INF||c[i]==INF)continue;ans=max(ans,(int)(upper_bound(c+1,c+n+1,c[i])-lower_bound(c+1,c+n+1,c[i])));}cout<<ans+cnt<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

分數解法

#include <bits/stdc++.h> #define ll long longusing namespace std;int aa[200005],ab[200005]; struct node {ll a,b; }rr[200005]; bool cmp(node a1, node a2) {if(a1.a == a2.a){return a1.b < a2.b;}return a1.a < a2.a; }int main() {int n;scanf("%d",&n);int cnt = 0, d0 = 0, a0 = 0, b0 = 0;for(int i = 0; i < n; ++i){scanf("%d",&aa[i]);}for(int i = 0; i < n; ++i){scanf("%d",&ab[i]);if(aa[i] == 0){++a0;//�κ�d��������if(ab[i] == 0){++d0;//�κ�d������++b0;//d����0������}}else if(ab[i] == 0){++b0;}else{ll g = __gcd(aa[i],ab[i]);rr[cnt].a = (long long)aa[i]/g;rr[cnt].b = (long long)ab[i]/g;if(rr[cnt].a < 0){rr[cnt].a *= -1;rr[cnt].b *= -1;}cnt++;}}sort(rr,rr+cnt,cmp);int ans = 0,cc = 1;if(cnt > 0){ans = 1;}for(int i = 1; i < cnt; ++i){if(rr[i-1].a * rr[i].b == rr[i-1].b * rr[i].a){cc++;ans = max(ans,cc);}else{cc = 1;}}printf("%d\n",max(b0,d0+ans));return 0; }

?

總結

以上是生活随笔為你收集整理的Zero Quantity Maximization的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。