本文主要是介绍Loan Repayment//二分//排位3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Loan Repayment//二分
题目
Farmer John owes Bessie N gallons of milk (1≤N≤1012). He has to give her the milk within K days. However, he doesn’t want to give the milk away too quickly. On the other hand, he has to make forward progress on the loan, so he must give Bessie at least M gallons of milk each day (1≤M≤1012).
Here is how Farmer John decides to pay back Bessie. He first picks a positive integer X. He then repeats the following procedure every day:
Assuming that Farmer John has already given Bessie G gallons, compute N−G/X rounded down. Call this number Y. If Y is less than M, set Y to M. Give Bessie Y gallons of milk. Determine the largest X such that if Farmer John follows the above procedure, Farmer John gives Bessie at least N gallons of milk after K days (1≤K≤1012).
Input
The only line of input contains three space-separated positive integers N, K, and M satisfying K⋅M<N.
Output
Output the largest positive integer X such that Farmer John will give Bessie at least N gallons using the above procedure.
Example
inputCopy
10 3 3
outputCopy
2
Note
For the first test case, when X=2 Farmer John gives Bessie 5 gallons on the first day and M=3 gallons on each of the next two days.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a “long long” in C/C++).
题意
n份牛奶k天还完，每天不能少于m份，假设已经给了g份，下一次不小于(n-g)/x,求x最大值
思路
利用二分搜索枚举x的值然后进行验证
代码
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#define pi 3.1415926
using namespace std;
typedef long long ll;
const ll inf=100000000000;
ll n,m,k;
bool check(ll x){ll g=0,time=k;while(g<n&&time>0){ll y=(n-g)/x;if(y<m){if(m*time>=n-g) return true;else return false;}ll temp=(n-g-x*y)/y+1;if(temp>k)temp=k;g+=y*temp;time-=temp;}if(g>=n)return true;else return false;
}
int main()
{scanf("%lld%lld%lld",&n,&k,&m);ll l=1,r=1e12;while(r>l){ll mid=(r+l+1)/2;if(check(mid))l=mid;elser=mid-1;}printf("%lld\n",l);return 0;
}
注意
处理好二分边界
这篇关于Loan Repayment//二分//排位3的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
