题解：P9789 [ROIR 2020 Day 2] ATM

zjc5 · 2024-08-21 19:54:08 · 题解

题目链接

思路：

设 f_i 是用 a_1\text{\textasciitilde}a_i 凑出小于 a_{i+1} 的面额所用最大纸币数，mx_i 表示符合此条件的最小值。

设 a_{i+1}-1=ka_i+b。

综上所述，mx_i=\lfloor\frac{a_{i+1}-mx_{i-1}-1}{a_i}\rfloor a_i+mx_{i-1}。

注意到若 a_i 的系数不能为零，则选出的 a_t 必须满足 a_{t+1}\gt a_t+mx_{t-1}。

查询答案时二分查找到满足 a_p\le b_i 的最大的 p，求答案的过程与预处理类似。

时间复杂度：

因为 a_t\gt mx_{t-1}\gt a_{t-1} 所以 a_t\lt \frac{a_{t+1}}2，又因为 a_t\le a_n 则 t\le 2\log(a_n)+1。

所以总时间复杂度是 O(n+q\log(\min(\log(a_n),n)))。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int n,t,b[N],a[N],q,x,f[N],mx[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    a[n+1]=2e18;
    for(int i=1;i<=n;i++){
        if(a[i]+mx[t]<a[i+1]){
            b[++t]=a[i];
            f[t]=f[t-1]+(a[i+1]-mx[t-1]-1)/b[t];
            mx[t]=(a[i+1]-mx[t-1]-1)/b[t]*b[t]+mx[t-1];
        }
    }
    cin>>q;
    while(q--){
        cin>>x;
        int p=upper_bound(b+1,b+t+1,x)-b-1;
        x=min(x,mx[p]);
        cout<<mx[p-1]+(x-mx[p-1])/b[p]*b[p]<<" "<<f[p-1]+(x-mx[p-1])/b[p]<<"\n";
    }
    return 0;
}