生活随笔
收集整理的這篇文章主要介紹了
HDU - 6278 Just $h$-index主席树+二分
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
HDU - 6278 Just hhh-index
【題目描述】
【題目分析】
題目要求在區間[l,r][l,r][l,r]內大于h的數不少于h個，對于這種最大化問題，我們應該想到二分。
最小情況顯然是1.最大情況顯然是r?l+1r-l+1r?l+1，對于一個hhh，我們如何判斷能否滿足條件呢？
我們可以用主席樹方便的求出區間第h大，如果區間第h大大于等于h，那么就能滿足條件
比較傷心的是我雖然一開始就想到了正確的思路但是區間第k大卻寫錯了。因為之前一直寫的是將所有數據都放在結構體中，所以一個賦值就講所有數據復制了，但是這次我想寫簡單一點，就將計數的數組放在了外面，然后在創建新節點的時候卻忘記了復制，導致瘋狂wa，還一直找不到為什么，啊啊啊，最終還是調試找到了
【AC代碼】（沒有借鑒其他人的，嘿嘿）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<climits>
#include<string>
#include<cmath>
#include<cstdlib>using namespace std
;const int MAXN
=100005;
int a
[MAXN
];
int n
,m
;
struct node
{int ls
,rs
;
}tree
[MAXN
*40];
int root
[MAXN
*40];
int cnt
[MAXN
*40];
int top
;void Insert(int &k
,int x
,int l
,int r
)
{tree
[++top
]=tree
[k
]; cnt
[top
]=cnt
[k
];cnt
[top
]++; k
=top
;if(l
==r
) return;int mid
=(l
+r
)>>1;if(x
<=mid
) Insert(tree
[k
].ls
,x
,l
,mid
);else Insert(tree
[k
].rs
,x
,mid
+1,r
);
}int query(int i
,int j
,int k
,int l
,int r
)
{if(l
==r
) return l
;int tmp
=cnt
[tree
[j
].rs
]-cnt
[tree
[i
].rs
];int mid
=(l
+r
)>>1;if(k
<=tmp
) return query(tree
[i
].rs
,tree
[j
].rs
,k
,mid
+1,r
);else return query(tree
[i
].ls
,tree
[j
].ls
,k
-tmp
,l
,mid
);
}int main()
{int u
,v
,l
,r
,mid
,ans
;while(~scanf("%d%d",&n
,&m
)){memset(cnt
,0,sizeof(cnt
));memset(root
,0,sizeof(root
));memset(tree
,0,sizeof(tree
));top
=0;for(int i
=1;i
<=n
;i
++){scanf("%d",&a
[i
]);root
[i
]=root
[i
-1];Insert(root
[i
],a
[i
],1,n
);}for(int i
=0;i
<m
;i
++){scanf("%d%d",&u
,&v
);l
=1; r
=v
-u
+1;while(l
<=r
){mid
=(l
+r
)>>1;if(query(root
[u
-1],root
[v
],mid
,1,n
)>=mid
){ans
=mid
;l
=mid
+1;}else{r
=mid
-1;}}printf("%d\n",ans
);}}return 0;
}
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的HDU - 6278 Just $h$-index主席树+二分的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
