題干：

時間限制:10000ms

單點(diǎn)時限:1000ms

內(nèi)存限制:256MB

描述

有一種叫作hohahola的飲料，售價是X元一瓶。小Hi非常喜歡這種飲料，但是他現(xiàn)在身無分文。

不過小Hi有N張優(yōu)惠券，買hohahola時每瓶最多使用一張優(yōu)惠券，可以使該瓶價格減少Y元。(Y ≤ X) ?

同時優(yōu)惠券可以出售，小Hi每出售一張優(yōu)惠券可以獲得Z元。 ?

請你幫小Hi計算通過出售若干優(yōu)惠券，他最多可以買多少瓶hohahola。

輸入

一行4個整數(shù)N, X, Y, Z。 ?

1 ≤ N, Z ≤ 1000000000 1 ≤ Y ≤ X ≤ 1000000000

輸出

一個整數(shù)表示答案

樣例輸入

100 3 2 1

樣例輸出

50

解題報告：

? ?不難發(fā)現(xiàn)，z>=y的時候，我們把優(yōu)惠券全都用來換成錢比較好。反之，可以猜測全都用來當(dāng)做優(yōu)惠用可以得到最優(yōu)解。（證明也不難證明但是因為是反之，，所以就可以猜了嘛）

? ?簡單說明一下，首先我們知道這題的關(guān)鍵在于優(yōu)惠券怎么使用。如果換錢，相當(dāng)于送給我們Z元，如果當(dāng)成優(yōu)惠來用，其實也可以想象成送給我們Y元。所以可以認(rèn)為兩個方案是等價的。具體哪種使用，就看這兩個值那個大就行了。有了這個結(jié)論，check就簡單多了。。其實二分的目的有的時候就是把變量，未知量很多的問題轉(zhuǎn)化成帶一個定值的，有的時候幫助理清思路。

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) {//能用來優(yōu)惠的都用來優(yōu)惠。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 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【hihocoder - offer编程练习赛60 A】hohahola（贪心，二分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。