贪心+树状数组，CF1579E2 - Array Optimization by Deque

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

很好想也很好证明的贪心

因为添加的顺序是确定的，我们每次只需决策放左边还是放右边

x放左边，那么贡献就是右边比x小的个数

x放右边，那么贡献就是左边比x大的个数

两个位置，哪个贡献少放哪边

证明：反证法

假设存在最优解，存在a[i] 没有按照贪心策略放置，不妨假设应该放左边P1但是放了右边P2

那么我们将操作修改把a[i]放左边P1，其它操作不变

那么a[i]只影响了a[P1 + 1, P2 - 1]之间的数字的贡献

由于贪心策略是放P1，所以区间内比a[i]小的个数小于等于比a[i]大的个数，所以贡献不会变大

我们不断调整最优解中不是贪心策略的操作能够得到另一个最优甚至更优解。

证毕

由于值域很大需要离散化

2、复杂度

时间复杂度：O(NlogN) 空间复杂度：O(N)

3、代码详解

​

#include <bits/stdc++.h>
using PII = std::pair<int, int>;
using i64 = long long;
 
const int inf = 1e9;

template<typename T = int>
class FenWick {
private:
    T n;
    std::vector<T> tr;
public:
    FenWick(T _n) : n(_n), tr(_n + 1) 
    {}

    void add(T x, T k) {
        for (; x <= n; x += x & -x) tr[x] += k;
    }

    T query(T x) const {
        T res = 0;
        for (; x; x &= x - 1) res += tr[x];
        return res;
    }
};
 
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> nums(n);
    for (int i = 0; i < n; i ++ ) std::cin >> nums[i];
    std::vector<int> id(nums);
    std::sort(id.begin(), id.end());
    id.erase(std::unique(id.begin(), id.end()), id.end());
    int m = id.size();
    
    FenWick<int> st(m + 1);

    i64 res = 0;
    for (int x : nums) {
        x = std::lower_bound(id.begin(), id.end(), x) - id.begin() + 1;
        int L = st.query(x - 1), R = st.query(m) - st.query(x);
        st.add(x, 1);
        res += std::min(L, R);
    }
    std::cout << res << '\n';
}
 
 
int main () {
    std::ios::sync_with_stdio(false);   std::cin.tie(0);  std::cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_ --)
        solve();
    return 0;
}