題意 ：

• 給$n$個$a_i$，在數軸找$n+1$個點，使得${\sum }_{i=1}^{n}2?a_i?|x_0?x_i|$最小

思路 ：

• 貪心，直接把$x_0$放在0點，$a_i$越大的離$x_0$越近
• sort的系數greater()實現從大到小的效果
• 方案一 ：除了原數組外再開一個數組p，對p進行排序，p[i]表示第i大的元素在原先數組中的下標，奇偶下標分別遍歷一次，res[i]表示原數組中下標為i的元素放的位置，1，3，5，分別對應位置是1，2，3。然后再遍歷累加得到答案；使用vector定長數組的好處 ：不浪費空間，且可以直接根據下標輸入，不需要pb
• 方案二 ：結構體（或者pair），第一個存$a_i$，第二個存原先的下標，再開一個數組，數組下標表示原先id，然后放入對應應該輸出的值，配合l和r雙指針，根據奇偶性放

// 方案一 #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> #define endl '\n' #define fi first #define se secondusing namespace std; using ll = long long;void solve() {int n; cin >> n;vector<int> a(n + 1);vector<int> p(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i], p[i] = i;sort(p.begin() + 1, p.end(), [&](int x, int y){return a[x] > a[y]; // a[p[i]] > a[p[j]]});vector<int> res(n + 1);res[0] = 0;for (int i = 1; i <= n; i += 2) res[p[i]] = (i + 1) / 2;for (int i = 2; i <= n; i += 2) res[p[i]] = -(i + 1) / 2;ll sum = 0;for (int i = 1; i <= n; i ++ ) sum += 2ll * a[i] * abs(res[i]);cout << sum << endl;for (int i = 0; i <= n; i ++ ) cout << res[i] << " \n"[i == n]; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; } // 方案二 #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #define endl '\n' #define fi first #define se secondusing namespace std; using ll = long long;const int N = 2e5 + 10;typedef pair<int, int> PII;PII a[N]; int p[N];void solve() {int n; cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i].fi, a[i].se = i;sort(a + 1, a + n + 1, greater<PII>());p[0] = 0;int l = -1, r = 1;ll sum = 0;for (int i = 1; i <= n; i ++ ){if (i % 2){sum += 2ll * a[i].fi * r;p[a[i].se] = r ++ ;}else{sum += 2ll * a[i].fi * (-l);p[a[i].se] = (l -- );}}cout << sum << endl;for (int i = 0; i <= n; i ++ ) cout << p[i] << " \n"[i == n]; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; }

總結

以上是生活随笔為你收集整理的Divan and a New Project 贪心，模拟(1000)的全部內容，希望文章能夠幫你解決所遇到的問題。

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