刷题记录:NC15322强迫症的序列

传送门:牛客
题目描述:

小A是一个中度强迫症患者,每次做数组有关的题目都异常难受,他十分希望数组的每一个元素都一样大,这样子看起来才
是最棒的,所以他决定通过一些操作把这个变成一个看起来不难受的数组,但他又想不要和之前的那个数组偏差那么大,
所以他每次操作只给这个数组的其中n-1个元素加1,但是小A并不能很好的算出最优的解决方案,如果你能帮他解决这个
问题,小A就能送你一个气球
输入:
1
3
1 2 3
输出:
3 4
1
2
3
4
5
6
7
8
9
10

主要思路:

1. 这道题刚开始我没有想到很好的一个解决思路,看了一眼难度竟然是1星题,然而我感觉似乎有点复杂,当时我是这么思考的,显然我们应该每次都将最少的几个加加,这就需要我们每次累加之后都需要一个排序,感觉似乎成为了一道平衡树的他题目,实现起来有一点点的麻烦,先不说对于n=100000会不会超时,对于一道一星题,我肯定是不愿意话时间去这么做出.
2. 然后我仔细看了一下题目,题目中描述增加元素的个数是全部元素个数减一,这时我们用离散的思想思考了一下就会发现,其他的值增加不就等于将另外的一个数的值减少一吗,这样来说的话那么事情就变得简单了起来,如果将modify的方式改成将一个数减少1的话,就直接排个序累加一下差值就可以轻松解决,还有因为贪心的思想,我们肯定是以最小的那一个作为基准线的,因此每一次减少的时候最小的那一个我们是不做改变的,因此最后的相同元素我们反过来得到的就是最小到元素加上改变的次数

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
int T;
int a[100005];
int main() {
	T=read();
	while(T--) {
		memset(a,0,sizeof(a));
		int n;n=read();
		for(int i=1;i<=n;i++) a[i]=read();
		sort(a+1,a+n+1);
		int sum=0;
		for(int i=2;i<=n;i++) {
			sum=sum+a[i]-a[1];
		}
		printf("%d %d\n",sum,a[1]+sum);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40