NC223140. 取钱
描述
某个国家的货币体系里有 种面值不同的纸币，从小到大面值分别是
，
。
当取款人去 机取款
元的时候，
机按一种贪心的策略给取款人发放钞票，策略如下：
首先，已发放钞票的集合是空集，每一次 机都会放一张当前可以放的最大面值的钞票进去，一直到集合里纸币面额等于
，然后将集合里的纸币吐给取款人。
现在这个国家的公民觉得用钱把裤兜装的满满的会很有面子，但是他们又不想取出太多钱。现在他们问你：在最多取 元的情况下，最多可以获得多少张纸币。
输入描述
第一行一个正整数
，表示钞票的面值数
第二行
，表示
第三行一个正整数
，表示公民询问的数量
接下来
输出描述
对于每个查询输出两个数字：取款的金额以及获得的纸币数量
若在不超过
的情况下有多个金额取款获得的纸币数量都是最大值，输出任意一个金额即可
示例1
输入:
4 1 5 10 50 3 2 8 50
输出:
2 2 8 4 49 9
C++ 解法, 执行用时: 209ms, 内存消耗: 16336K, 提交时间: 2021-07-09 19:55:26
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
int n,q;
ll a[maxn],x;
ll k[maxn],s[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
k[i]=(a[i+1]-s[i-1]-1)/a[i];
s[i]=s[i-1]+k[i]*a[i];
k[i]+=k[i-1];
}
scanf("%d",&q);
while(q--){
scanf("%lld",&x);
int p=upper_bound(s,s+n,x)-s-1;
ll m=(x-s[p])/a[p+1];
printf("%lld %lld\n",s[p]+m*a[p+1],k[p]+m);
}
}