【hihocoder - offer编程练习赛60 A】hohahola（贪心，二分）

题干：

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

 

总结

以上是生活随笔为你收集整理的【hihocoder - offer编程练习赛60 A】hohahola（贪心，二分）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。