当前位置:网站首页>Bzoj4240: interesting family garden (tree array)

Bzoj4240: interesting family garden (tree array)

2020-12-07 14:36:29 osc_ vqbasmql

Subject portal
.

solution :
The subscript of the original array is 1~n.
After disruption, the number of exchanges is in reverse order .
Because one exchange will produce a reverse pair ..
The number of pairs in reverse order should be as small as possible .



It's about a mountain ?
It's something that's high in the middle and diminishing on both sides .
So sort by height .
Look at whether the insertion on the left or on the right produces fewer reverse pairs .
Greed



Code implementation :

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
struct node {
  
  int id,x;}a[310000];int s[310000];
int lowbit(int x) {
  
  return x&-x;}int n;
void change(int x) {
  
  while(x<=n) {s[x]++;x+=lowbit(x);}}
int find_sum(int x) {
  
  int ans=0;while(x>0){ans+=s[x];x-=lowbit(x);}return ans;}
bool cmp(node n1,node n2) {
  
  return n1.x>n2.x;}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
  
  scanf("%d",&a[i].x);a[i].id=i;}
    sort(a+1,a+1+n,cmp);ll ans=0;memset(s,0,sizeof(s));
    for(int i=1;i<=n;) {
        int x=i;
        for(;x<=n;x++) {
            int t=find_sum(a[x].id);ans+=min(t,i-1-t);
            if(a[x].x!=a[x+1].x)break;
        }
        for(;i<=x;i++)change(a[i].id);
    }printf("%lld\n",ans);
    return 0;
}

版权声明
本文为[osc_ vqbasmql]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012071434170659.html