蓝桥杯2023年-阶乘的和（数学推理，C++）

题目描述

给定 n 个数 Ai，问能满足 m! 为∑ni=1(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1 × 2 × 3 × · · · × m。

思路

我们发现m最大为所有A中的最小值，但是如果有Ai+1个Ai相同，则他们可以合并为Ai+1，

即：A!*(A+1)=(A+1)!，所以我们可以先从小到大对A进行合并，让A的最小值尽可能大，最后剩下的最小值就是m所能取到的最大值了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n;cin>>n;
    map<int,int>mp;
    priority_queue<int,vector<int>,greater<int>>q;
    for(int i=0;i<n;i++){
        int a;cin>>a;
        mp[a]++;
        q.push(a);
    }
    while(q.top()+1<=mp[q.top()]){
        int t=q.top();
        int k=q.top()+1;
        q.push(t+1);
        mp[t+1]++;
        while(k--){
            q.pop();
            mp[t]--;
        }
    }
    cout<<q.top();
     
}
signed main(){
    int T=1;
    // cin>>T;
    while(T--){
        solve();
    }
}