T244841 分配学号 题解

原题传送门 （鸡尾酒的原创题！请谨慎转载）

题目描述

给定一些数，其中有一些相同的数字，现在需要修改其中的一些数字（只增不减），并且使得修改后所有数字的总和减去原来所有数字的总和最小，求按这样的要求修改有多少种不同的方式。

思考

要想知道怎样修改，我们就要先知晓最终的答案是那几个数。让我们来观察几组样例寻找规律。

请注意，这里的样例中的数字都是从小到大给出的，便于后续的观察与计算。然而题目中可没有保证数据一定是递增的！

样例 1

3
1 1 2

显而易见，最终的学号应该变为 1 2 3 。

样例 2

5
1 2 2 2 3

最终的学号应该变成 1 2 3 4 5 。到这里，我们似乎找到了一些规律：假设有 $n$ 个数，最终的序列必定是 1, 2, 3, ..., n-1, n 。真的是这样吗？让我们来看下一个样例。

样例 3

5
1 1 2 7 7

请注意，该样例仅仅在 样例1 后面加上了两个数。按照刚才的出来的结论，最终的序列是 1 2 3 4 5 吗？显然不是。虽然 1 1 2 能变成 1 2 3 ，但是 7 7 并不能成为 4 5 ，因为数字只增不减。对于这种特殊情况，我们不妨称之为“断点”。当出现断点时，原本的递增序列的当前值小于该位置的真实值（断点的定义）。在断点处，我们需要重新开始计算一段序列。就比如在 2 和 7 之间就是一个端点。前三个数字的 1 2 3 没有问题，但是从 7 开始，序列就应该变成 7 8 。我们可以简单归纳为，“基数”从 1 变成了 7 。

再来明确一点：对于每一个断点分开的区间，其最终形成的理想序列仅适用于当前区间。如 样例3 中，前一段 1 1 2 只可能变成 1 2 3 ，具体哪个数字变成哪一个无所谓，但是不能有任意一个变成 7 8 ，不然后面的两个数字就不能完全满足其变化的需求了。

有了这些铺垫，让我们来计算答案。

使用乘法原理

现在我们仅来关注一个区间。来看样例：

3
1 1 2

我们都知道，最终的序列会变成 1 2 3 。那么，如何计算其中的方案数呢？

学过1+1的同学都知道，要计算乘法原理，我们要先从条件苛刻的数字算起。对于第一个数字 1 ，可以变成 1 、 2 或 3 ，有两种方案；第二个数字亦是如此。至于第三个数字 2 ，我们只能将其变成 2 或 3 ，只有两种方案。所以第三个数字 2 的条件比较苛刻。我们从 2 算起。现在 2 选走了一个数字，前面两个 1 就各剩下两种和一种。于是最终的方案数就是各个数字的方案数的乘积，也就是 $2 \times 2 \times 1 = 4$ 。

对于每一个数，它的方案数就是它与“基数”的差加上1。这样我们就能一路乘过去了。

对于每一个区间，利用如上的算法。那么最终的终极答案就是每一个区间的乘积了。下面让我们用代码来实现这一过程。

代码实现

• 首先最重要的一步，排序！！！别忘了我们之前一切推导都是建立在递增序列的基础上。

sort(a+1,a+1+n);

• 其次，让我们定义一个 last_max ，变量，用来记录基数以及当前的变化值。
  • 如果当前值在 last_max 的承受范围内，即 $a[i] \leq last_max + 1$ ，则让 last_max 自增 $1$ ，随后答案乘上 $last_max$ ；
  • 如果当前值超过了 last_max 的承受范围，说明这里出现了一个“断点”，则更新 last_max 的值为 $a[i]$ 。
• 在解答过程中别忘了取模。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,a[100010];
ll cnt=1;
ll last_max;
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	last_max=a[1];
	for(ll i=2;i<=n;i++){
		if(a[i]<=last_max+1){
			last_max++;
		}else{
			last_max=a[i];
		}
		cnt*=(last_max-a[i]+1)%mod;
		cnt%=mod;
	}
	cout<<cnt%mod<<endl;
	return 0;
}