HihoCoder1619 “共同富裕”（逆向思维）
“共同富裕”
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个数组A1, A2, ... AN，每次操作可以从中选定一个元素Ai，把除了Ai之外的所有元素都加1。
问最少几次操作可以实现“共同富裕”，即数组中所有元素都相等。
例如对于[1, 1, 1, 2, 3]经过3步:[1, 1, 1, 2, 3] -> [2, 2, 2, 3, 3] -> [3, 3, 3, 3, 4] -> [4, 4, 4, 4, 4]。
输入
第一行包含一个整数N。(1 ≤ N ≤ 100000)
以下N行包含N个整数A1, A2, ... AN。 (1 ≤ Ai ≤ 100000)
输出
最小的操作数
- 样例输入
-
5 1 1 1 2 3
- 样例输出
-
3
这道题和上道题是太简单了吗，10分钟就搞定了这两道，难道是期中的人品都留这里来辣，期中求一个及格，qwq
由于只有一个数不改变，其它都加一，而改变n-1个太麻烦，逆向考虑就是：只有一个改变---减一，其他不变。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> using namespace std; const int maxn=100010; int a[maxn],Min=maxn; long long ans; int main() { int i,j,n; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); Min=min(Min,a[i]); } for(i=1;i<=n;i++) ans+=a[i]-Min; printf("%lld",ans); return 0; }