CCPC-Wannafly & Comet OJ 夏季欢乐赛(2019) H 分配学号 (思维)

it2022-05-06  7

题目链接:https://cometoj.com/contest/59/problem/H

 

今天,是JWJU给同学们分配学号的一天!为了让大家尽可能的得到自己想要的学号,鸡尾酒让大家先从 [1,] 中随机挑选一个数字作为自己的学号。但是总有一些心有灵犀的小伙伴们选择了一样的数字——显然这样是不合法的,因为每个人的学号都应该是唯一的。

于是鸡尾酒决定调整大家的学号。他采用如下两个原则来修改:

1、只增不减,每个人的最终学号≥ 每个人初始选择的学号

2、总修改量尽量少,总修改量指每一个人的改动量之和。(改动量即为最终学号减初始学号的值)

注意,修改后的最终学号可以大于。

很显然,如果现在有两个同学 A 和 B,初始选择的学号均为1号,他们有可能被鸡尾酒改动成 A 同学为 1 号和 B 同学为 2 号,或者改动成 B 同学为 1号和 A 同学为 2 号。

鸡尾酒邪魅一笑,他想让你告诉他,大家的最终学号共有多少种不同的分配方案 模1e9+7。

 

 

官方题解:先排序,然后判断当前位置的同学的学号有几种选择的方案,累 乘获得结果。

标程:

#include <bits/stdc++.h> typedef long long lld; using namespace std; const int MAXN = 1e5+5; const int MOD = 1e9+7; int n; lld a[MAXN]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); sort(a, a+n); lld ans = 1; for (int i = 0, j; i < n; i = j) for (j = i+1; j < n && a[j] < a[i]+j-i; j++) ans = ans * (a[i]+j-i-a[j]+1) % MOD; printf("%lld\n", ans); return 0; }

思路:要求改动量之和最小,所以数字尽量的加的少,比如   1   1    2    3    7   7 

一种改法是    1    4   2   3    7     8  这样改动量之和为    4

可不可以把第一个1  改成5  或者  6  不可以  因为 数字大了  改动量也就变大了   

所以每一位的数可以选择的数字有

1   1   2   3   7    7

2   2   3   4   8    8

3   3   4   

4   4 

所以如何确定这些数字有哪些取法呢

可以发现每两个数让他们相差为1最好  但是比如这里的3  和 7   再怎么改也不能让3变为6  因为改大了 

但是 如果数列是   3  3 4 5 7 7   这样  就可以让5 变成6了  有什么发现呢

就是  一些数字的可以组成一个集合,让他们之间的差为1

然后计算一下有多少集合  然后再看每个集合里的数字有多少种情况  乘起来就好

如何分组呢

 还是拿之前的那个数列  1    1   2  3    7    7

这个很显然 1    1   2   3   一组    7   7 一组

用什么来区分呢  就是根据一个区间的最大值减去最小值+1  和区间长度做比较

[1,4]   max = 3,  min = 1, max-min+1 < 4 - 1 + 1   然而  [1,5] max = 7   ,min=1  , max-min+1 >5 - 1 + 1

简化来看就是   i-j>a[i]-a[j]  就可以分成一组

 分好了组 那么如何算结果呢 比如这个数列  1  1   2   3   7   7 的每个数的选择有 

1   1   2   3                7    7

2   2   3   4                8    8

3   3   4   

4   4   

先拿1  1   2  3  来看  比如第四位取3  那么第三位还有两种情况  ans*=2,第二位还有2种情况ans*=2,  第一位还有一种情况ans*=1

当第四位取4的时候  也是相同的情况  所以ans*=2,  对于7  7  这个一组来说同理  最后结果乘起来就行了

发现这规律就好比阶乘   或者组合数一样   

假设数列为  1  1   1    1    那么  一种情况就是   1  2  3  4 

每个数字的取值都是 {1  2  3   4 }  即都是4种, 那么结果就是   ans  = ans * 4 * 3 * 2 * 1

那么第四位是2种  第三位是3种,第二位4种  第一位4种  那么结果就是 

ans  = ans *min(4-0,2-0)*min(4-1,3-1)*min(4-2,4-2)*min(4-3,4-3);

 

 

#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #define ll long long using namespace std; const int maxn = 1e5+6; const ll mod = 1e9 + 7; vector<ll>v[maxn]; int n,cnt=0; ll a[maxn]; ll cnt1[maxn]; int main() { scanf("%d",&n); ll minn,maxx ; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } sort(a+1,a+n+1); v[0].push_back(a[1]); for(int i=2,j=1;i<=n;i++) { if(i-j>a[i]-a[j]){ v[cnt].push_back(a[i]); } else { cnt++; v[cnt].push_back(a[i]); j=i; } } for(int i=0;i<=cnt;i++) { maxx = v[i][0] + v[i].size()-1; cnt1[i]=maxx; for(int j=0;j<v[i].size();j++) { v[i][j]=maxx - v[i][j]+1; } sort(v[i].begin(),v[i].end()); } ll ans1=1; for(int i=0;i<=cnt;i++) { for(int j=0;j<v[i].size();j++) { ans1= ans1 * min(cnt1[i]-j,v[i][j]-j) %mod; } } printf("%lld\n",ans1); return 0; }

 


最新回复(0)