題意 ：

• 給一數組$c=[c_1,c_2,...,c_m]$，求構造一個長度為n的數組$a=[a_1,a_2,...,a_n]$，使得$?i\in [1,m]$恰好有$c_i$個$i$出現在數組$a$中
• 定義一個函數$f(a)={\sum }_{1\le i<j\le n,a_i=a_j}j?i$，求出$f(a)$的最大值，并且求出當$f(a)$最大時，$a$的構造方案

思路 ：

• 容易想到一個貪心，注意到相同的數字間的距離越遠，對答案的貢獻越大，于是對數字大小從大到小來考慮，每次都拿出兩個放到$a$兩邊，這就是構造方法
• 接下來考慮對答案的貢獻以及方案數的計算
• 首先考慮對答案的貢獻，設當前$a$中還有$num$個位置沒排，當前排個數為$i$的數，設有$cnt[i]$個，根據剛才的策略，容易得出對$i$從大到小考慮。首先就是這$cnt[i]$個數依次放到數組兩邊，那么每個數字的貢獻就是$$num?cnt[i]?2+cnt[i]$$一共有$cnt[i]$個數字，乘起來，最后還要算上兩邊對中間的$(i?2)?cnt[i]$個數的貢獻$$(i?2)?cnt[i]?(num?cnt[i]?2+cnt[i])$$化簡后就是$$(num?cnt[i])?cnt[i]?(i?1)$$ 每輪放數字結束后記得把$num?=2?cnt[i]$，因為有這么多的位置被占了
• 方案數的話就很簡單了，對當前個數為1的時候進行特判，因為這個只能放一邊，其他的都是可以兩邊隨意放，所以就是$cnt[i]!$種，乘法原理即可

#include <iostream> #include <vector>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<int> cnt(N);vector<ll> 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(); }

總結

以上是生活随笔為你收集整理的Max Sum Array 贪心（2500）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。