这道题还是很经典的
给出了一个序列,代表的是比该位置的牛靠前站的且序号比他小的牛的个数
然后思想类似于2828,正序看的话,看不出有什么规律,但是逆序的话,就能看出当前序列的最后一头牛的编号是可以确定的,就相当于有一个队列,初始化全为1,有牛占了就把相应位置变为0,然后我们只管那些位置为1的地方,往里一头一头的塞牛,塞一头,能塞的地方就少一个,但是和之前塞过的就没关系了,这也符合题目中,只管比该位置靠前的且序号小的 这个条件
/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10000
#define INF 1000000000
#define eps 1e-7
#define PI 3.1415926535898
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
int left, right, mid;
int cnt;
}tree[4 * MAXN];
int a[MAXN], ans[MAXN];
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) >> 1;
tree[C].cnt = tree[C].right - tree[C].left + 1;
if(s == e) return;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
void insert(int p, int x, int C)
{
tree[C].cnt--;
if(tree[C].left == tree[C].right)
{
ans[x] = tree[C].left;
return;
}
if(tree[L(C)].cnt > p)
insert(p, x, L(C));
else insert(p - tree[L(C)].cnt, x, R(C));
}
int main()
{
int n;
scanf("%d", &n);
make_tree(1, n, 1);
for(int i = 2; i <= n; i++)
scanf("%d", &a[i]);
for(int i = n; i >= 1; i--)
insert(a[i], i, 1);
for(int i = 1; i <= n; i++)
printf("%d\n", ans[i]);
return 0;
}
下面是树状数组做法
其实还是那个原理 ,倒序推。刚开始的时候把n个位置都准备好,然后塞牛,塞一头就把相关的位置删1,表示之前能站的地方少了一个。
然后倒序找位置的时候,用的是二分查找。因为树状数组的和,也是有序的
/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10000
#define INF 1000000000
using namespace std;
int a[MAXN];
int ans[MAXN];
int t[MAXN], n;
int lowbit(int x)
{
return x & -x;
}
void modify(int x, int v)
{
for(int i = x; i <= n; i += lowbit(i))
a[i] += v;
}
int getsum(int x)
{
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))
sum += a[i];
return sum;
}
int search(int x)
{
int low = 1;
int high = n;
int mid;
while(low <= high)
{
mid = (low + high) >> 1;
int tmp = getsum(mid);
if(x <= tmp) high = mid - 1;
else low = mid + 1;
}
return low;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
modify(i, 1);//把这些位置准备好,表示都可以站牛
for(int i = 2; i <= n; i++)
scanf("%d", &t[i]);
for(int i = n; i >= 1; i--)
{
ans[i] = search(t[i] + 1);
modify(ans[i], -1); //这头牛占了一个位置,把之后有关系的地方都删掉这个1
}
for(int i = 1; i <= n; i++)
printf("%d\n", ans[i]);
return 0;
}
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2430 Lazy Cows.md
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1747400
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
NULL 博文链接:https://128kj.iteye.com/blog/1745671
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1705139