题意:FJ有n头牛,编号为1~n,它们并没有按照编号的顺序排好队列。现在,FJ只知道每一个牛前面有多少只牛的编号比它大。问你能不能判断出所有牛的编号。
思路:线段树。关键:每次最后一只牛的编号是可以确定的,即为pre[i]+1,将其编号从所有牛中删除,则倒数第二只牛的编号又可以确定为pei[i]+1,依此类推。
代码如下:
#include<iostream>
using namespace std;
const int Max = 8005;
struct
{
int l, r, len; // 用len存储这个区间的数字个数。
}node[3*Max];
int pre[Max], ans[Max];
void BuildTree(int left, int right, int u)
{ // 建树。
node[u].l = left;
node[u].r = right;
node[u].len = right - left + 1;
if(left == right)
return;
BuildTree(left, (left+right)/2, 2*u);
BuildTree((left+right)/2+1, right, 2*u+1);
}
int query(int u, int num)
{ // 查询+维护,关键一点:所求值为当前区间的左起第num个元素。
node[u].len--; // 对访问到的区间维护len。
if(node[u].l == node[u].r)
return node[u].l;
// 情况1:左子区间的数字个数不够,则查询右子区间的左起第num - node[u<<1].len个元素。
if(node[2*u].len < num)
return query(2*u+1, num - node[2*u].len);
// 情况2:左子区间的数字个数足够,则依旧查询左子区间的左起第num个元素。
if(node[2*u].len >= num)
return query(2*u, num);
}
int main()
{
int n, i;
scanf("%d", &n);
pre[1] = 0;
for(i = 2; i <= n; i ++)
scanf("%d", &pre[i]);
BuildTree(1, n, 1);
for(i = n; i >= 1; i --) // 从后往前推断出每次最后一个数字。
ans[i] = query(1, pre[i]+1);
for(i = 1; i <= n; i ++)
printf("%d\n", ans[i]);
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
Poj中一些题目的源代码,里面共有二十多道题目,OI