简答题 偏难
#20267

奖品兑换 时间限制:1 s,内存限制:512 MB 【问题描述】 班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使…

奖品兑换

时间限制:1 s,内存限制:512 MB

【问题描述】

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。

具体来说,可以使用 a 张课堂优秀券和 b 张作业优秀券兑换一份奖品,或者使用 b 张课堂优秀券和 a 张作业优秀券兑换一份奖品。

现在小 A 有 n 张课堂优秀券和 m 张作业优秀券,他最多能兑换多少份奖品呢?

【输入描述】

第一行,两个正整数 n、m,分别表示小 A 持有的课堂优秀券和作业优秀券的数量。

第二行,两个正整数 a、b,表示兑换一份奖品所需的两种券的数量。

【输出描述】

输出共一行,一个整数,表示最多能兑换的奖品份数。

【样例输入1】

8 8
2 1

【样例输出1】

5

【样例输入2】

314159 2653589
27 1828

【样例输出2】

1599

【数据范围】

对于60%测试点,保证 1 <= a、b <= 100,1 <= n、m <= 500。

对于所有测试点,保证 1 <= a、b <= 10^4,1 <= n、m <= 10^9。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; int n, m, a, b; int l, r; int check(int v) {     long long x, y, t;     x = 1ll * v * a;     y = 1ll * v * b;     if (y &gt; m) {         t = (y - m + (b - a) - 1) / (b - a);         y -= t * (b - a);         x += t * (b - a);     }     return x &lt;= n &amp;&amp; y &lt;= m; } int main() {     cin &gt;&gt; n &gt;&gt; m &gt;&gt; a &gt;&gt; b;     if (n &gt; m)         swap(n, m);     if (a &gt; b)         swap(a, b);     if (a == b) {         cout &lt;&lt; n / a &lt;&lt; endl;         return 0;     }     l = 0;     r = n;     while (l &lt; r) {         int mid = (l + r + 1) &gt;&gt; 1;         if (check(mid))             l = mid;         else             r = mid - 1;     }     cout &lt;&lt; r &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。