Max Sum Array 贪心（2500）

题意 ：

• 给一数组 c = [ c 1 , c 2 , . . . , c m ] c=[c_1,c_2,...,c_m] c=[c1​,c2​,...,cm​]，求构造一个长度为n的数组 a = [ a 1 , a 2 , . . . , a n ] a=[a_1,a_2,...,a_n] a=[a1​,a2​,...,an​]，使得 ∀ i ∈ [ 1 , m ] forall i in [1,m] ∀i∈[1,m]恰好有 c i c_i ci​个 i i i出现在数组 a a a中
• 定义一个函数 f ( a ) = ∑ 1 ≤ i < j ≤ n , a i = a j j − i f(a)=sum_{1 leq i < j leq n,a_i=a_j}j-i f(a)=∑1≤i

思路 ：

• 容易想到一个贪心，注意到相同的数字间的距离越远，对答案的贡献越大，于是对数字大小从大到小来考虑，每次都拿出两个放到 a a a两边，这就是构造方法
• 接下来考虑对答案的贡献以及方案数的计算
• 首先考虑对答案的贡献，设当前 a a a中还有 n u m num num个位置没排，当前排个数为 i i i的数，设有 c n t [ i ] cnt[i] cnt[i]个，根据刚才的策略，容易得出对 i i i从大到小考虑。首先就是这 c n t [ i ] cnt[i] cnt[i]个数依次放到数组两边，那么每个数字的贡献就是 n u m − c n t [ i ] ∗ 2 + c n t [ i ] num-cnt[i]*2+cnt[i] num−cnt[i]∗2+cnt[i]一共有 c n t [ i ] cnt[i] cnt[i]个数字，乘起来，最后还要算上两边对中间的 ( i − 2 ) ∗ c n t [ i ] (i-2)*cnt[i] (i−2)∗cnt[i]个数的贡献 ( i − 2 ) ∗ c n t [ i ] ∗ ( n u m − c n t [ i ] ∗ 2 + c n t [ i ] ) (i-2)*cnt[i]*(num-cnt[i]*2+cnt[i]) (i−2)∗cnt[i]∗(num−cnt[i]∗2+cnt[i])化简后就是 ( n u m − c n t [ i ] ) ∗ c n t [ i ] ∗ ( i − 1 ) (num-cnt[i])*cnt[i]*(i-1) (num−cnt[i])∗cnt[i]∗(i−1) 每轮放数字结束后记得把 n u m − = 2 ∗ c n t [ i ] num-=2*cnt[i] num−=2∗cnt[i]，因为有这么多的位置被占了
• 方案数的话就很简单了，对当前个数为1的时候进行特判，因为这个只能放一边，其他的都是可以两边随意放，所以就是 c n t [ i ] ! cnt[i]! cnt[i]!种，乘法原理即可

#include 
#include 

using namespace std;
using ll = long long;

const int N = 1e6 + 10;
const ll MOD = 1e9 + 7;

inline void solve()
{
    int n; cin >> n;
    vector cnt(N);
    vector f(N);
    
    ll num = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int x; cin >> x;
        num += x;   // num表示一共有多少个位置要放东西
        cnt[x] ++ ;     // cnt数组表示个数为x的数有多少种
    }
    
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) f[i] = f[i - 1] * i % MOD;   // 计算阶乘 f[i] = i!
    
    ll res = 0, ways = 1;       // 最大值和方案数
    for (int i = 1000000; i; i -- )     // 个数 1000000 -> 1
    {
        cnt[i] += cnt[i + 2]; // 注意，之前的数都只排了两个，肯定有剩下的，所以需要隔位后缀和
        if (i == 1) ways = ways * f[cnt[i]] % MOD;  // 特判个数为1的数，如果个数1（被迫放在同一边），就是 (cnt[1]!)
        else ways = ways * f[cnt[i]] % MOD * f[cnt[i]] % MOD;   // 否则，是 (cnt[i]!) * (cnt[i]!) （两边位置和）
        res = (res + (num - cnt[i]) * cnt[i] % MOD * (i - 1) % MOD) % MOD;
        num -= 2 * cnt[i];
    }
    
    cout << res << ' ' << ways << endl;
}

int main()
{
    cin.tie(nullptr) -> sync_with_stdio(false);
    
//    int _;
//    cin >> _;
//    while (_ -- )
        solve();
}