【QED】烦人的图书

题目

题目链接🔗

题目描述

自从达利园来到广东工业大学揭阳校区就读后，她就发现她特别喜欢“天圆地方”的图书馆。达利园是一个特别特别喜欢读书的人，在她看来读书就要从头读到尾，不能读到一半就放弃，也不能直接从中间开始读，这些行为都是令她烦恼的，所以她觉得每一个系列的书借阅的次数应该都是一样多的才行。现在她在系统里发现有好几个系列的书借阅次数参差不齐，于是她决定去通过自己借阅的方式，把每一个系列的图书借阅次数借到一样多！！！

假设图书馆里有图书一共 $T$ 个系列，其中一个系列的图书会有 $n$ 本书，每一本书已经借阅次数分别为： $A_1,A_2,...,A_n$ （借阅次数不小于0），达利园每一次都会抱这个系列中的 $n-1$ 本图书去一楼进行一次借阅（要留下一本书方便记录这些书是放在哪里的），对于这 $n-1$ 本书，借阅次数全部加 $1$，剩余的那一本图书借阅次数不增加，每一次借阅完毕她都会把书放回原来的位置。

试问对于每一个系列的图书，达利园至少需要多少次才能将他们的借阅次数提升至相同的次数呢？达利园不想计算，你来写一个程序帮帮她叭~

输入描述

第一行包含一个数 $T$，表示该图书馆里面一共有多少种系列的图书

接下来会有 $T(1\le T\le 10^2)$ 组数据：

每一组数据的第一行包含一个数 $n(1\le n\le 10^7)$ ，表示这一个系列的图书一共有多少本

每一组数据的第二行包含个数 $A_1,A_2,...,A_i,...,A_n$ 表示该系列第 $i$ 本书的借阅次数$(0\le A_i\le 2^{32}-1)$

数据保证$\sum n\le 10^7$

输出描述

输出 $T$ 行，每行一个数表示达利园需要借阅的次数，结果可能很大，请对 $10^9+7$ 取模

测试用例

input1

2
3
1 2 3
2
4 5

output1

3
1

思路

转换一下思维，每一本书都借一遍就是大家都没借。如果有$n-1$本书借了一遍就相当于有一本书借阅次数少了一次，这样子的话我们可以很轻松的以借阅次数最少的那一本作为基准，对其他的书进行操作，每一次把其中一本书的借阅次数减一。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll t,a[10000010];
int main(){int n;scanf("%lld",&t);long long minzhi;while(t--){minzhi=INT_MAX;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);minzhi=min(a[i],minzhi);//找出借阅次数最少的那一本书}long long ans=0;for (int i = 1; i <= n; i++) {ans += a[i] - minzhi;ans %= mod;}printf("%lld\n",ans);}return 0;
}

复杂度分析

时间复杂度

于每个系列，遍历所有书以找到最小借阅次数需要 $O(n)$，然后再次遍历计算总操作次数也需要 $O(n)$。因此，每个系列的时间复杂度为 $O(n)$。由于总书本数的限制，整体时间复杂度为 $O(\sum n)$，其中 $\sum n\le 10^7$

空间复杂度

需要一个大小为 $n$ 的数组来存储每个系列的借阅次数，因此空间复杂度为 $O(n)$

总结

通过每次选择 $n-1$ 本书进行借阅，达利园可以逐步将所有书的借阅次数调整到与当前最小借阅次数相同。计算每本书需要增加的借阅次数之和，即可得出使所有书的借阅次数相等所需的最小操作次数