最临近神的人_NOI导刊二〇一〇提升

2019-11-11 19:41 来源:未知

P1774 最相近神的人_NOI导刊2010提高(02),p1774_noi

难题陈诉

破解了符文之语,小FF开启了向阳地下的征程。当他走到最终面部分时,发掘正前方有意气风发扇巨石门,门上雕刻着生机勃勃幅古人举行某种活动的绘画。而石门上方用金朝文写着“神的神殿”。小FF猜测里面应该就有朝廷的遗产了。但今后的标题是怎样展开那扇门……

周到切磋后,他意识门上的图案差十分少是说:古代人认为唯有智者才是最轻易临近佛祖的。而最明白的人再三经过风流倜傥种仪式选择出来。仪式大约是指,将在隐退的聪明人为她的候选人写下大器晚成串严节的数字,并让她们开展大器晚成种操作,即交流系列中相邻的五个因素。而用起码的置换次数使原系列产生不减弱类别的人就是下生龙活虎任智者。

小FF发掘门上雷同享有n个数字。于是她以为展开这扇门的要诀正是找到让这几个队列形成不减少类别所必要的小不点儿次数。但小FF不会……只能又找到了您,并承诺事成之后与你三八分……

输入输出格式

输入格式:

 

率先作为三个卡尺头n,表示系列长度

第二行为n个整数,表示系列中各样元素。

 

出口格式:

 

叁个整数ans,即起码操作次数。

 

输入输出样例

输入样例#1:

4
2 8 0 3

出口样例#1:

3
   样例说明:开始序列为2 8 0 3,目标序列为0 2 3 8,可进行三次操作的目标序列:
    1.Swap (8,0):2  0  8  3
    2.Swap (2,0):0  2  8  3
    3.Swap (8,3):0  2  3  8

说明

对于30%的数据1≤n≤10^4。

对于100%的数据1≤n≤5*10^5;

-maxlongint≤A[i]≤maxlongint。

 

那题用合并列排在一条线序可以水过。

只是自个儿用了树状数组+离散化+二分

率先,树状数组中存的是小于等于当前职分的数的个数

我们先把原本的数组排序,然后每趟利用二分的主意求出待求的数在排好序的连串中现身的职位

那是因为是按顺序枚举,所以我们每一次默许有i个数比正在枚举的数大,那么大家用树状数组找寻小于当前数的个数就可以

末尾后生可畏减便是答案

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define lli long long int 
 7 using namespace std;
 8 const lli MAXN=2000001;
 9 lli lowbit(lli p)
10 {
11     return p&-p;
12 }
13 void read(lli &n)
14 {
15     char c='+';lli x=0;bool flag=0;
16     while(c<'0'||c>'9')
17     {c=getchar();if(c=='-')flag=1;}
18     while(c>='0'&&c<='9')
19     {x=x*10+(c-48);c=getchar();}
20     flag==1?n=-x:n=x;
21 }
22 lli a[MAXN];
23 lli tree[MAXN],mp[MAXN];
24 lli n;
25 lli query(lli p)
26 {
27     lli tot=0;
28     while(p)
29     {
30         tot+=tree[p];
31         p=p-lowbit(p);
32     }
33     return tot;
34 }
35 void add(lli p)
36 {
37     while(p<=MAXN/2)
38     {
39         tree[p]++;
40         p+=lowbit(p);
41     }
42 }
43 int erfen(int num)
44 {
45     int l=1,r=n;
46     while(l<r)
47     {
48         int mid=(l+r)>>1;
49         if(mp[mid]==num)
50             return mid;
51         if(mp[mid]>num)
52             r=mid-1;
53         if(mp[mid]<num)
54             l=mid+1;
55     }
56     return l;
57 }
58 int main()
59 {
60 //    memset(tree,0,sizeof(tree));
61     read(n);
62     lli ans=0;
63     for(lli i=1;i<=n;i++)
64     {
65         read(a[i]);
66         mp[i]=a[i];
67     }
68     sort(mp+1,mp+n+1);
69     for(int i=1;i<=n;i++)
70     {
71         int p=erfen(a[i]);
72         add(p);
73         ans+=i-query(p);
74     }
75     printf("%lld",ans);
76     return 0;
77 }

 

最周边神的人_NOI导刊2010提高(02),p1774_noi 标题叙述破解了符文之语,小FF开启了通向地下的征程。当她走到最尾部时,发现正前方...

TAG标签:
版权声明:本文由990888藏宝阁发布于网络应用,转载请注明出处:最临近神的人_NOI导刊二〇一〇提升