《P13013 [GESP202506 五级] 奖品兑换》

题目背景对应的选择、判断题试题 - 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≤1001≤n,m≤500。对于所有测试点保证 1≤a,b≤1041≤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) { // 修复ab必须同时满足两种券足够 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; }