文章目錄

• 題目描述
• 輸入描述
• 輸出描述
• 輸入輸出樣例
• 最終代碼c/c++
• 過程理解

題目描述

n個小朋友站成一排。現在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個小朋友。

每個小朋友都有一個不高興的程度。開始的時候，所有小朋友的不高興程度都是 0。

如果某個小朋友第一次被要求交換，則他的不高興程度增加 1，如果第二次要求他交換，則他的不高興程度增加 2（即不高興程度為 3），依次類推。當要求某個小朋友第 k 次交換時，他的不高興程度增加 k。

請問，要讓所有小朋友按從低到高排隊，他們的不高興程度之和最小是多少。

如果有兩個小朋友身高一樣，則他們誰站在誰前面是沒有關系的。

輸入描述

輸出描述

輸出一行，包含一個整數，表示小朋友的不高興程度和的最小值

輸入輸出樣例

輸入：

3 3 2 1

輸出：

9

---

最終代碼c/c++

#include <bits/stdc++.h> using namespace std; const int N = 1000010; typedef long long LL; int h[N], tree[N], k[N]; //h是身高，k是交換次數（逆序對數量） int lowbit(int x) { return x & -x; } void update(int x, int d) {while(x <= N) {tree[x] += d;x += lowbit(x);} } int sum(int x) {int ans = 0;while(x > 0){ans += tree[x];x -= lowbit(x);}return ans; } int main() {int n; cin >> n;for (int i = 1; i <= n; i ++ ){cin >> h[i];h[i]++; //h從1開始，不是從0開始}for (int i = 1; i <= n; i ++ ) { //正序處理 逆序對，右邊矮的k[i] = sum(N - 1) - sum(h[i]);update(h[i], 1);}memset(tree, 0, sizeof tree);for (int i = n; i; i-- ){ //倒序處理 逆序對，左邊高的k[i] += sum(h[i] - 1);update(h[i], 1);}LL res = 0;for (int i = 1; i <= n; i ++ ) //最后把所有人的不愉快加起來res += (LL)k[i] * (k[i] + 1 ) / 2;cout << res;return 0; }

---

過程理解

總結

以上是生活随笔為你收集整理的13.1 数状数组 ——【小朋友排队】的全部內容，希望文章能夠幫你解決所遇到的問題。

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