//
// Created by 罗炳国 on 2023/6/12.
//

#ifndef PFJ_SMARTSUM_H
#define PFJ_SMARTSUM_H

#include "commonHeader.h"

// 小和问题
/*
 * 在一个数组中，一个数左边比它小的数的总和，叫该数的小和
所有数的小和累加起来，叫数组小和
例子： [1,3,4,2,5]
1左边比1小的数：没有
3左边比3小的数：1
4左边比4小的数：1、3
2左边比2小的数：1
5左边比5小的数：1、3、4、 2
所以数组的小和为1+1+3+1+1+3+4+2=16
给定一个数组arr，求数组小和
 *
 * */


class smartSum {
public:
    int getSmartSum(vector<int> &arr) {
        return 0;
    }

    int getSmartSumRight(vector<int> &arr) {
        int ret = 0;
        int N = arr.size();
        for (int i = 0; i < N; i++) {
            int target = arr[i];
            for (int j = 0; j < i; j++) {
                if (arr[j] < target)
                    ret += arr[j];
            }
        }
        return ret;
    }

    void test() {
        vector<int> arr {1,3,4,2,5};
        int ans = getSmartSumRight(arr);
        std::cout << ans << std::endl;
    }
private:
    int process(vector<int> &arr, int l, int r) {
        if (l == r) return 0;
        int m = l + ((r - l) >> 1);
        return 0;
    }

    int merge(vector<int> &arr, int l, int m, int r) {
        return 0;
    }
};

#endif //PFJ_SMARTSUM_H