暴力做法（60分）
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],b[N]; int n,k,sum; bool judge(int x) { //倍数判断 int ans=0; for(int i=0;i<n;i++) { int x1=a[i]/x; int y1=b[i]/x; ans+=x1*y1; } if(ans>=k) return true; return false; } int main() { scanf("%d%d",&n,&k); for(int i=0;i<n;i++) { scanf("%d%d",&a[i],&b[i]); sum+=a[i]*b[i]; } sum/=k; //printf("%d",sum); for(int i=1;i<=sum/i+1;i++) { if(!judge(i)) { printf("%d",i-1); break; } } return 0; }
二分做法（100分）
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],b[N]; int n,k,sum; bool judge(int x) { //倍数判断 int ans=0; for(int i=0;i<n;i++) { int x1=a[i]/x; int y1=b[i]/x; ans+=x1*y1; } if(ans>=k) return true; return false; } int main() { scanf("%d%d",&n,&k); for(int i=0;i<n;i++) { scanf("%d%d",&a[i],&b[i]); sum+=a[i]*b[i]; } sum/=k; int l=1,r=100000; while(r>l) { int mid=(l+r+1)/2; if(!judge(mid)) r=mid-1; else l=mid; } printf("%d",l); return 0; }
从左往右找第一个不可以/可以的数字 <模板>
int l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] <= x) l = mid; else r = mid - 1; }
从右往左找第一个不可以/可以的数字 <模板>
int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (q[mid] >= x) r = mid; else l = mid + 1; }