E2. Array Optimization by Deque（树状数组 + 离散化 + 贪心）

本文主要是介绍E2. Array Optimization by Deque（树状数组 + 离散化 + 贪心），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：E2. Array Optimization by Deque

https://codeforces.com/contest/1579/problem/E2

题意：给出一个数组，依次将数组元素插入到双端队列中，每次插入可以选择插入队首或者队尾，问插入后队列中的逆序数最小值是多少。

输入：第一行输入测试用例个数t。

      t个测试用例，每个测试用例第一行输入数组元素个数n（1 <= n <= 2e5）,第二行 给出数组的n个元素ai(-1e9 <= ai <= 1e9)。

输出：输出可构造的双端队列逆序数的最小值。

样例输入：

1

3 7 5 5

样例输出：

2

样例解释：可构造双端队列：【3 7 5 5】、【5 3 7 5】、【5 5 3 7】。

问题分析：树状数组 + 离散化 + 贪心。

求逆序数有分治法、树状数组、线段树。本题需要动态插入元素，故分治法不适用。而树状数组与线段树相比较容易实现，故采用树状数组来求逆序数。因为元素范围过大，故需要对数组进行离散化。

解题步骤：先用STL的vector和unique函数可以较简单得对数组进行离散化。在选择元素插入到双端队列队首或者队尾时，只需要判断插入到队首所增加的逆序数和插入到队尾所增加的逆序数哪个小就选择哪个，若相等，则任意选择队首或队尾。在插入的过程中累加元素所增加的逆序数即可得到答案。

贪心示例：若当前双端队列的元素有1 3 5，下一个要插入的元素是4

      若插入队首：4 1 3 5   所增加的逆序数是2个（4 ， 1）， （4 ， 3）。

      若插入队尾：1 3 5 4   所增加的逆序数是1个（5， 4）。

      所以应该将4插入到队尾。

贪心策略粗略证明：之所以该贪心策略是正确的，是因为每个元素所增加的逆序数只与插入到队首或队尾有关，而与前面的元素的顺序无关，即元素所增加的逆序数之间相互独立。

      比如双端队列中有三个元素1 3 5，顺序不确定。 即可能为【3 1 5】，【5 3 1】等，但插入元素4到队首所增加的逆序数必为2，插入元素4到队尾所增加的逆序数必为1，因为3 1 5这三个元素是连续的。

AC代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 2e5 + 10;

ll a[N], tr[N], n, ans;

ll lowbit(ll x){

           return x & (-x);

}

ll sum(ll x){

           int res = 0;

           while(x >= 1){

              res += tr[x];

              x -= lowbit(x);

           }

           return res;

}

void add(ll x, int num){

           while(x <= n){

              tr[x] += num;

              x += lowbit(x);

           }

}

void solve(){

           ans = 0;

           memset(tr, 0, sizeof(tr));

           scanf("%lld", &n);

           vector<ll> v;

           for(int i = 1;i <= n;i++){

              scanf("%lld", &a[i]);

              v.push_back(a[i]);

           }

           sort(v.begin(), v.end());

           v.erase(unique(v.begin(), v.end()), v.end());

           map<ll, int> p;

           for(int i = 0;i < v.size();i++){

              p[v[i]] = i + 1;

           }

           map<ll, int> p2;

           for(int i = 1;i <= n;i++){

              add(p[a[i]], 1);

              p2[a[i]]++;

              ans += min(sum(p[a[i]]) - p2[a[i]], i - sum(p[a[i]]));

           }

           printf("%lld\n", ans);

}

int main(void){

           int t;

           scanf("%d", &t);

           while(t--) solve();

           return 0;

}

时间复杂度：O（nlogn）。

空间复杂度：O（n）。

这篇关于E2. Array Optimization by Deque（树状数组 + 离散化 + 贪心）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！