就是二分查找就够了, 找到符合条件的那个最小值
不会二分可以去学一下, 可以看看这个: https://www.cnblogs.com/wzl19981116/p/9354012.html
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<cmath>
- #include<cstring>
- #include<map>
- #include<vector>
- #include<queue>
- #include<stack>
- #define sf scanf
- #define scf(x) scanf("%d",&x)
- #define scff(x,y) scanf("%d%d",&x,&y)
- #define scfff(x,y,z) scanf("%d%d%d",&x,&y,&z)
- #define vi vector<int>
- #define mp make_pair
- #define pf printf
- #define prf(x) printf("%d\n",x)
- #define mm(x,b) memset((x),(b),sizeof(x))
- #define rep(i,a,n) for (int i=a;i<n;i++)
- #define per(i,a,n) for (int i=a;i>=n;i--)
- typedef long long ll;
- int in(){
- int x=0,f=1; char ch;
- while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
- return f*x;}
- using namespace std;
- const ll mod=1e9+7;
- const double eps=1e-6;
- const double pi=acos(-1.0);
- const int inf=0x7fffffff;
- const int N=1e5+7;
- ll n,m,a[N];
- bool judge(ll t)
- {
- ll s=0;
- rep(i,0,n)
- {
- s=s+t/a[i];
- }
- return s>=m;
- }
- int main()
- {
- cin>>n>>m;
- rep(i,0,n)
- cin>>a[i];
- ll l=0,r=100000000009;
- while(r-l>1)
- {
- ll mid=(l+r)/2;
- if(judge(mid))
- r=mid;
- else
- l=mid;
- }
- while(judge(r)) r--;
- r++;
- cout<<r;
- return 0;
- }
小测 D
来源: http://www.bubuko.com/infodetail-2876879.html