题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1430
题意: 求x,y使得ax + by <= n (x>=0, y>=0)且ax+by尽量大。
思路:
假设a > b,只需要暴力枚举x判断即可,上限top为min(n/a, b),复杂度是O(sqrt(n))的。
证明很简单,如果x > b则可以写成 a(x + b) + by = ax + ab + by = ax + b(a+y),这里的x < b,即这种情况肯定是枚举到了的,所以上限设为min(n/a, b)。
code: