题解 | #C 取钱#

思路：见代码

#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;
}