思路:见代码
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 200010; int n, q; LL a[N]; LL f[N]; LL g[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]); a[n + 1] = 1e18 + 1; //用面额 a[i] 凑 a[i+1] 最多能凑的纸币数量, 贪心原则 优先面额小的(可以多凑数) for (int i = 1; i <= n; ++ i) { LL cnt = (a[i + 1] - f[i - 1] - 1) / a[i]; f[i] += f[i - 1] + cnt * a[i]; // 凑的数量最多时钱的总价(必需小于a[i+1]) g[i] += g[i - 1] + cnt; // 当前面额i能凑不超过面额i+1的最多数量 //cout << f[i] << " " << g[i] << endl; } scanf("%d", &q); while(q--) { LL num; scanf("%lld", &num); int p = upper_bound(a + 1, a + n + 1, num) - a - 1; // 找到小于当前钱的最大面额 a[p] printf("%lld %lld\n", f[p - 1] + (num - f[p - 1]) / a[p] * a[p], g[p - 1] + (num - f[p - 1]) / a[p]); // 凑钱方式同上,由于当前要凑的钱可以等于所以不能-1 } return 0; }