自动搬运

查看原文

来自洛谷，原作者为

	zjc5 zjc

搬运于2025-08-24 22:51:52，当前版本为作者最后更新于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$。

1. $mx_{i-1}\le b$，显然 $mx_i=ka_i+mx_{i-1}$。
2. $mx_{i-1}\gt b$，则所有 $ka_i+c(0\le c\le b)$ 的纸币数必然小于 $k+f_{i-1}$，即小于等于 $k-1+f_{i-1}$，而 $k-1+f_{i-1}$ 刚好对应 $(k-1)a_i+mx_{i-1}$。

综上所述，$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;
}