首页 > 代码库 > poj2182-Lost Cow
poj2182-Lost Cow
题目链接 http://vjudge.net/problem/POJ-2182
解题思路
用最朴素的想法，从尾到头扫描，再开两个循环找空位，时间复杂度O（n3），容易超时。
正确的做法是建立线段树。维护每个区间的长度。长度足够排下就往左子树走，否则往右子树。
直到叶子节点，此时叶子节点的区间（点）为此奶牛的编号。
代码
#include<stdio.h>#define MAX_SIZE 10010struct Node { int l, r; int len;}tree[4*MAX_SIZE];int small[MAX_SIZE], q[MAX_SIZE];void BuildTree(int root, int left, int right){ if(left == right) { tree[root].l = tree[root].r = right; tree[root].len = 1; return ; } tree[root].l = left; tree[root].r = right; tree[root].len = right - left + 1; int mid = (left + right) / 2; BuildTree(root*2, left, mid); BuildTree(root*2+1, mid+1, right);}int query(int root, int s){ tree[root].len--; if(tree[root].l == tree[root].r) return tree[root].l; if(tree[root*2].len >= s) return query(root*2, s); else return query(root*2+1, s - tree[root*2].len);}int main(){ int n; scanf("%d", &n); for(int i=2; i<=n; i++) scanf("%d", &small[i]); small[1] = 0; BuildTree(1, 1, n); for(int i=n; i>=1; i--) q[i] = query(1, small[i]+1); for(int i=1; i<=n; i++) printf("%d\n", q[i]); return 0;}
poj2182-Lost Cow
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。