题解 | #取钱#

贪心思路：对于a[i]尽可能多的取，然后再尽可能多的取a[i+1]
sum表示a[1]~a[i-1]取的总钱数，cnt表示总张数
对于a[i]取的张数x需要满足

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int q, n;
ll a[N], s;
pair<ll, ll> ans[N];

struct node {
    ll q, ans, cnt;
    int id;

    bool operator<(const node &b) const {
        return q < b.q;
    }
} query[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
    a[n + 1] = 1e18 + 1;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)scanf("%lld", &query[i].q), query[i].id = i;
    sort(query + 1, query + 1 + q);
    ll s = 1e18;
    ll sum = 0, res = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        if ((s - sum) < a[i])break;
        ll x = (a[i + 1] - sum - 1) / a[i];
        while (j <= q && sum + a[i] * x >= query[j].q) {
            ll k = (query[j].q - sum) / a[i];
            query[j].cnt = res + k;
            query[j].ans = sum + k * a[i];
            j++;
        }
        if (j > q)break;
        res += x;
        sum += a[i] * x;
    }
    while (j <= q) {
        query[j].cnt = res;
        query[j].ans = sum;
        j++;
    }
    for (int i = 1; i <= q; i++)
        ans[query[i].id] = {query[i].ans, query[i].cnt};
    for (int i = 1; i <= q; i++)
        printf("%lld %lld\n", ans[i].first, ans[i].second);
    return 0;
}