首页 > 代码库 > POJ 2182 Lost Cows (树状数组 && 二分查找)
POJ 2182 Lost Cows (树状数组 && 二分查找)
题意:给出数n, 代表有多少头牛, 这些牛的编号为1~n, 再给出含有n-1个数的序列, 每个序列的数 ai 代表前面还有多少头比 ai 编号要小的牛, 叫你根据上述信息还原出原始的牛的编号序列
分析:如果倒着看这个序列的话, 那序列的最后一个元素就能够确定一个编号。举个例子：如果序列的最后一个元素为0, 那就说明这头牛前面再也没有比它编号更小的牛了, 所以这头牛的编号肯定是最大的, 我们只要给它所在的编号加个标记, 然后继续根据倒数第二个、第三个……来依次确定便可还原整个序列, 这里可以使用树状数组做, 初始化全部加1操作, 然后开始枚举编号, 看哪个编号前面是有多少比其编号小的牛, 即区间求和, 一旦和一开始给出的序列元素相同则确定是此编号, 确定一头之后便抹去这头牛的编号, 即add(num, -1), 时时更新即可, 但是这里如果用for循环去枚举和的话未免太慢, 但也能AC, 这里考虑使用二分查找便很快了!
瞎搞:这题实际上还可以用线段树做, 做法大同小异, 但没想到的是, 这还是一个DP可以解决的题目……
树状数组:
#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<algorithm> #include<stack> #define lowbit(i) (i&(-i)) #define LL long long using namespace std; int c[8001]; int ans[8001]; int n; inline void add(int i, int val) { while(i<=n){ c[i] += val; i += lowbit(i); } } int sum(int i) { int ans = 0; while(i>0){ ans += c[i]; i -= lowbit(i); } return ans; } int Bin_search(int L, int R, int key) { int mid; while(L < R){ mid = L + ((R-L)>>1); if(sum(mid)-1 < key) L = mid+1; else R = mid; } return R; } int main(void) { scanf("%d", &n); memset(c, 0, sizeof(c)); stack<int> st; st.push(0); for(int i=1; i<=n-1; i++){ int temp; scanf("%d", &temp); st.push(temp); add(i, 1); } add(n, 1); int top = 0; while(!st.empty()){ int temp = st.top(); st.pop(); int num = Bin_search(1, n, temp); ans[top++] = num; add(num, -1); } for(int i=top-1; i>=0; i--){ printf("%d\n", ans[i]); } return 0; }
线段树:
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; typedef struct segment { int L, R, len; }T;///线段树类型 int a[10000], result[10000];///a储存input，result储存output T tree[30000];///线段树数组 ///------------------------------------ void init(int, int, int); int query(int, int); ///------------------------------------ int main(void) { std::ios::sync_with_stdio(false);///关闭同步，加快读入速度 int n; cin>>n; a[1] = 0;///第一个前面不可能有比它小的数 for(int i=2; i<=n; i++){ cin>>a[i]; } init(1, 1, n);///(root, L, R) for(int i=n; i>=1; i--){ result[i] = query(1, a[i]+1); } for(int i=1; i<=n; i++) cout<<result[i]<<endl; return 0; } ///-------------------------------------------- void init(int root, int L, int R)///给线段树初始化从1~n的数据 { tree[root].L = L; tree[root].R = R; tree[root].len = R-L+1; if(L == R) return ; init(2*root, L, (L+R)/2); init(2*root+1, (L+R)/2+1, R); } ///-------------------------------------------- int query(int node, int aim) { tree[node].len--; if(tree[node].L == tree[node].R) return tree[node].L; if(aim <= tree[2*node].len) return query(node*2, aim); else return query(node*2+1, aim-tree[node*2].len); }
POJ 2182 Lost Cows (树状数组 && 二分查找)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。