LOJ#2873「JOISC 2014 Day1」有趣的家庭菜园 题解

First Post:

Last Update:

给定一个序列, 一次操作是交换相邻两个数. 问最少交换多少次使得数列是单峰的. .

我们定义一个数列 的值为 . 对于一个序列, 记 , .

有结论: 答案就是那个序列的值.

首先, 我们发现答案一定不小于序列的值. 这是因为考虑一次操作所改变的数列的值, 最多会使数列的值减少 1. (最多改变操作的两个数中较小数的 ).

接下来我们构造一组合法的解. 我们可以这样做: 从小到大考虑每个数, 如果其 , 那么将其向左交换直到 . 否则向右交换直到 . 我们发现对于每个数, 交换的次数就是 . 所以答案就是 .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 300005
map<int, int> H; int n; pir h[_];
int c[_<<1], L[_], R[_]; ll ans;
#define lowbit(x) (x&(-x))
void add(int p, int x) { for(; p<=n; p+=lowbit(p)) c[p]+=x; }
int query(int p) { int res=0; for(; p; p-=lowbit(p)) res+=c[p]; return res; }
int main() {
  rd(n); f(i,1,n) { rd(h[i].fir); h[i].sec=i; } sort(h+1, h+n+1);
  f(i,1,n) {
    H[h[i].fir] = h[i].fir == h[i-1].fir ? H[h[i-1].fir] : H[h[i-1].fir] + 1;
  }
  sort(h+1, h+1+n, [](pir x, pir y){return x.sec<y.sec;});
  f(i,1,n) { L[i]=i-1-query(H[h[i].fir]); add(H[h[i].fir], 1); }
  memset(c, 0, sizeof(c));
  d(i,1,n) { R[i]=n-i-query(H[h[i].fir]); add(H[h[i].fir], 1); }
  f(i,1,n) ans += min(L[i], R[i]);
  cout << ans << endl;
  return 0;
}