FilesExpand file tree

 master

/

1394.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

108 lines (91 loc) · 1.86 KB

 master

/

1394.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

108 lines (91 loc) · 1.86 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

#include <iostream>

#include <list>

using namespace std;

const int MAXN = 6000;

const int INF = 999999999;

int N, tree[MAXN*8];

//,data[MAXN];

list<int> data;

void pushUp(int idx){

tree[idx] = tree[idx*2]+tree[idx*2+1];

}

void clear(){

memset(tree,0,sizeof(tree));

}

void build(int l, int r, int idx){

if(l==r){

tree[idx] = 0;

return;

}

int m = (l+r)>>1;

build(l,m,idx*2);

build(m+1,r,idx*2+1);

pushUp(idx);

}

int query(int L,int R, int l, int r, int idx){

if(L<=l && R>=r ){

return tree[idx];

}

int m = (l+r)>>1;

int ret1=0, ret2=0;

if(L<=m){

ret1 = query(L, R, l, m, idx*2);

}

if(R>=m+1){

ret2 = query(L, R, m+1, r, idx*2+1);

}

return ret1+ret2;

}

void update(int L, int R, int l, int r, int idx){

if(L<=l && R>=r){

tree[idx] += 1;

return;

}

int m = (l+r)>>1;

if(L<=m){

update(L, R, l, m, idx*2);

}

if(R>m){

update(L, R, m+1, r, idx*2+1);

}

pushUp(idx);

}

void work(){

int cnt_N = N;

int ans = INF;

build(1,N, 1);

int sum = 0;

list<int>::iterator it;

for(it = data.begin(); it!=data.end(); it++){

int t = query(*it+2, N, 1, N, 1);

sum += t;

update(*it+1, *it+1, 1, N, 1);

}

ans = sum;

cnt_N-=1;

while(cnt_N--){

int ttt = 3;

int front = data.front();

front+=1;

data.pop_front();

data.push_back(front);

int smaller = front-1;

int larger = N-front;

sum -= smaller;

sum += larger;

ans = min(sum, ans);

}

cout<<ans<<endl;

}

int main(){

while(scanf("%d",&N)!=EOF){

data.clear();

int tmp;

for(int i=0; i<N; i++){

scanf("%d",&tmp);

data.push_back(tmp);

}

work();

}

return 0;

}