本文主要是介绍HDOJ-4006/(大连网赛1006)- The kth great number 剖析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文不想废话，直接上多种做法。
题意：固定的k，动态加点，动态询问第k大数。
一、树状数组+二分
这里有两种做法，一种是二分sum(i)，另一种是利用二进制二分逼近k。
树状数组常用来处理区间点的统计情况，这里n没有规定大小（理论上是int32），但是操作次数n是小于1000,000的，所以可以先进行离散化来储存1000,000个点值（我不知道这是不是所谓的离散化，因为点本身是整数，但是，这至少是一种散列、一种映射，异曲同工的）。
具体操作为，先读入样例中出现的所有点，然后排序，insert( lower_bound(list, list+n, a[i])-list+1 ) 。a[]为原始数列，list为排序后数列，+1为了避免下标为0。至此便完成了离散化。
返回第k大数：
① 二分sum(i)，利用二分查找的思想，目标为 tot-sum(ans) < k <= tot-sum(ans-1)。sum()为树状数组的求和操作。要注意的是，树状数组中c[x]记录的是x的权值，也就是有c[x]个数同为x，则在查找第k大数的时候不一定是正好的，不能按原始的二分查找的模式，这里WA了好多次......
② 二进制二分逼近，本来是受以下二者启发，
http://tieba.baidu.com/f?kz=1033300126
http://www.cnblogs.com/zgmf_x20a/archive/2008/11/15/1334109.html用来求第k小数的，显然已知总点数的情况下可以用来求得第k大数。
但是后来发现第一种的版本是错的，
代码类似
int ans=0;for(int i=1<<log2(all); i; i>>=1){if(c[ans+i] <= k){k-=c[ans+=i];}}return ans;我因为这个WA了好久，有两个错误，①改成 if(c[ans+i] < k)，最后return ans+1。理由同上面红字。 ② if 中还要加上 ans+i<all &&...
代码（两种方法合在一起，见注释）：
//hdoj-4006，动态求第k大数 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;#define MAXN 1000005 #define LOWBIT(x) x&(-x) int a[MAXN]; //原数组，最多1000000个数 int list[MAXN]; //排序数列 int q[MAXN]; //是否询问：Q int c[MAXN]; int n, k, all;int log2(int x) { int i=0; for(; x; x>>=1, i++); return i-1; } void insert(int x) {while(x<=all){c[x]+=1;x+=LOWBIT(x);} } /// 方法一：二进制，二分逼近 int find_kth_small(int k) {int ans=0;for(int i=1<<log2(all); i; i>>=1){if(ans+i<all && c[ans+i] < k) //！！！{k-=c[ans+=i];}}return ans+1;/* //这个一样int cnt=0, ans=0;for(int i=1<<log2(all); i; i>>=1){ans+=i;if(ans>=all || cnt+c[ans]>=k) ans-=i;else cnt+=c[ans];}return ans+1;*/ } int find_kth_great(int k, int tot) {return find_kth_small(tot-k+1); } /// 方法二：二分sum(i) int sum(int i) {int res=0;for(; i>0; i-=LOWBIT(i)){res+=c[i];}return res; }int search(int k) //!!目标是 tot-sum(ans) < k <= tot-sum(ans-1)，而普通的二分查找目标是k=a[ans]. {int l=1, r=all;int tot = sum(r);while(l<=r){int mid = (l+r)/2;if(tot-sum(mid)>=k){l = mid+1;}else if(tot-sum(mid)<k && k<=tot-sum(mid-1)){return mid;}else{r = mid-1;}}/* //这个也是对的，但是我感觉上面的好理解while(l<=r){int mid = (l+r)/2;if(tot-sum(mid-1)>=k) l=mid+1;else r = mid-1;}return l-1;*/ }int main() {while(cin>>n>>k){memset(c, 0, sizeof(c));memset(q, 0, sizeof(q));all = 0; //记录总共加入的数for(int i=0; i<n; i++){char t[2];cin>>t;if(t[0] == 'I'){int x; cin>>x;a[i] = x; //a[] 原数列list[all++] = x; //加入的数列，之后要经过排序，方便散列}else if(t[0] == 'Q'){q[i] = 1;}}sort(list, list+all);int tot=0;for(int i=0; i<n; i++){if(!q[i]){tot++;insert(lower_bound(list, list+all, a[i])-list+1); //+1，避免0下标}else{ // cout<<list[search(k)-1]<<endl; //第一种，二进制二分逼近cout<<list[find_kth_great(k, tot)-1]<<endl; //第二种，二分sum(i)}}} }
二、建堆
做一个小顶堆，放k个元素。每insert一个数，如果此数大于堆顶，就插入堆，并去掉原堆顶，如果小于则不操作，因为无影响。这个就是利用了这个题目的特殊性，即一个样例中k是固定不变的，不像其他题目可能会输入"Q k"这样作为一条指令。也因此造就了本场比赛第一水题。（掩面.....）
众所周知，优先队列（priority_queue）是用二叉堆实现的，下面给出STL优先队列的版本：
#include<iostream> #include<queue> #include<vector> using namespace std; struct cmp {bool operator() (int a, int b) {return a<b? 0: 1;} }; priority_queue<int, vector<int>, cmp> q; //或者直接使用，greater<int> int n, k;int main() {while(cin>>n>>k){while(n--){char t[2]; cin>>t;if(t[0] == 'I'){int x; cin>>x;if(q.size()<k) q.push(x);else if(x > q.top()) {q.pop(); q.push(x); }}else{cout<<q.top()<<endl;}}} }
三、
【待续...】
这篇关于HDOJ-4006/(大连网赛1006)- The kth great number 剖析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
