题干:

时间限制: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 ;
 }