题解 | #计算数组的小和#
计算数组的小和
https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469
learning follow 左程云老师 https://github.com/algorithmzuo/algorithm-journey
改了下左老师计算小和的逻辑,Merge行为只用遍历一遍,代价是从只算加法变为需要乘法。
#include <bits/stdc++.h> using namespace std; using ll = long long; ll Merge(int* arr, int* temp, int l, int m, int r) { ll ans = 0, cur = l; int p1 = l, p2 = m + 1; while (p1 <= m && p2 <= r) { if (arr[p1] <= arr[p2]) { ans += arr[p1] * (r - p2 + 1); temp[cur++] = arr[p1++]; } else { temp[cur++] = arr[p2++]; } } while (p1 <= m) { temp[cur++] = arr[p1++]; } while (p2 <= r) { temp[cur++] = arr[p2++]; } for (int i = l; i <= r; i++) { arr[i] = temp[i]; // cout << arr[i] << " "; } // cout << "ans=" << ans << endl; return ans; } ll SmallSum(int* arr, int* temp, int l, int r) { ll ans = 0; if (r > l) { int m = (l + r) / 2; ans = SmallSum(arr, temp, l, m) + SmallSum(arr, temp, m + 1, r) + Merge(arr, temp, l, m, r); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); // start from here int n; cin >> n; int arr[n], temp[n]; for (auto&& i : arr) { cin >> i; } cout << SmallSum(arr, temp, 0, n - 1); return 0; }
}