题干:
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
有一种叫作hohahola的饮料,售价是X元一瓶。小Hi非常喜欢这种饮料,但是他现在身无分文。
不过小Hi有N张优惠券,买hohahola时每瓶最多使用一张优惠券,可以使该瓶价格减少Y元。(Y ≤ X)
同时优惠券可以出售,小Hi每出售一张优惠券可以获得Z元。
请你帮小Hi计算通过出售若干优惠券,他最多可以买多少瓶hohahola。
输入
一行4个整数N, X, Y, Z。
1 ≤ N, Z ≤ 1000000000 1 ≤ Y ≤ X ≤ 1000000000
输出
一个整数表示答案
样例输入
100 3 2 1
样例输出
50
解题报告:
不难发现,z>=y的时候,我们把优惠券全都用来换成钱比较好。反之,可以猜测全都用来当做优惠用可以得到最优解。(证明也不难证明但是因为是反之,,所以就可以猜了嘛)
简单说明一下,首先我们知道这题的关键在于优惠券怎么使用。如果换钱,相当于送给我们Z元,如果当成优惠来用,其实也可以想象成送给我们Y元。所以可以认为两个方案是等价的。具体哪种使用,就看这两个值那个大就行了。有了这个结论,check就简单多了。。其实二分的目的有的时候就是把变量,未知量很多的问题转化成带一个定值的,有的时候帮助理清思路。
AC代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll n,x,y,z;
bool ok(ll t) {
//能用来优惠的都用来优惠。
ll tmp = min(n,t);
return (n-tmp) * z >= tmp*(x-y) + (t-tmp)*x ;
}
int main()
{
cin>>n>>x>>y>>z;
if(z >= y) {
printf("%lld\n",n*z / x);return 0 ;
}
ll l = 0,r = 1e9;
ll mid = (l+r)>>1,ans = 0;
while(l<=r) {
mid = (l+r)>>1;
if(ok(mid)) l = mid+1,ans = mid;
else r = mid-1;
}
cout << ans;
return 0 ;
}