企业官网建设流程全解析

题目背景

对应的选择、判断题：试题 - GESP 202506 C++ 五级 - 洛谷有题

为了保证只有时间复杂度正确的代码能够通过本题，时限下降为 400 毫秒。

题目描述

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。具体来说，可以使用 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≤104，1≤n,m≤109。

代码实现;

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n, m, a, b; ll ceil_div(ll num, ll den) { if (num >= 0) return (num + den - 1) / den; else return num / den; } ll floor_div(ll num, ll den) { if (num >= 0) return num / den; else return (num - den + 1) / den; } bool check(ll x) { if ((a + b) * x > n + m) return false; ll L = 0, R = x; if (a == b) { // 修复：a==b必须同时满足两种券足够 return (a * x <= n) && (a * x <= m); } if (a > b) { ll d = a - b; ll up = n - x * b; R = min(R, floor_div(up, d)); ll down_num = x * a - m; ll low = ceil_div(down_num, d); L = max(L, low); } else { ll d = b - a; ll down_num = x * b - n; ll low = ceil_div(down_num, d); L = max(L, low); ll up = m - x * a; R = min(R, floor_div(up, d)); } return L <= R; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; cin >> a >> b; ll l = 0, r = (n + m) / (a + b), ans = 0; while (l <= r) { ll mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << "\n"; return 0; }