Poj 2182-Lost Cows(Treap||树状数组+二分答案)

题目链接:点击打开链接

题意:n个牛编号为1-n 现在编号顺序已经打乱,给出a[i] ,a[i] 代表i位置前面有几个小于它的编号,求编号顺序。

倒着推,对于最后一个a[i] , 最后位置编号肯定是 a[i]+1,然后在1-n个编号中删掉当前编号,继续往前推。。即求第 a[i]+1小数,初始容器中有n个数(1-n) ,每求出来一个就删掉。先用平衡树水了一发。。明天写树状数组解法。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 8005
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1<<40+10
#define pp pair<int,int>
#define ull unsigned long long
using namespace std;
int n,ans[maxn];
struct node{
	node *ch[2];
	int r,v,s;
	node (){}
	node (int v){ch[0]=NULL;ch[1]=NULL;r=rand();this->v=v;s=1;}
	bool operator <(const node& c)const{
		return r<c.r;
	}
	int cmp(int x)const {
		if(x==v)return -1;
		return x<v?0:1;
	}
	void maintain(){
		s=1;
		if(ch[0]!=NULL)s+=ch[0]->s;
		if(ch[1]!=NULL)s+=ch[1]->s;
	}
};
void rotate(node* &o,int d){
	node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
	o->maintain();k->maintain();o=k;
}
void insert(node* &o,int x)
{
	if(o==NULL) o=new node(x);
	else{
		int d=o->cmp(x);
		insert(o->ch[d],x);
		if(o->ch[d]->r>o->r)rotate(o,d^1);
	}
	o->maintain();
}
void remove(node* &o,int x)
{
	int d=o->cmp(x);
	if(d==-1){
		node* u=o;
		if(o->ch[0]!=NULL&&o->ch[1]!=NULL){
			int d2=(o->ch[0]->r>o->ch[1]->r?1:0);
			rotate(o,d2);remove(o->ch[d2],x);
		}
		else{
			if(o->ch[0]==NULL)o=o->ch[1];
			else o=o->ch[0];
			delete u;
		}
	}
	else
	remove(o->ch[d],x);
	if(o!=NULL) o->maintain();
}
bool find(node* o,int x)
{
	while(o!=NULL)
	{
		int d=o->cmp(x);
		if(d==-1)return 1;
		else o=o->ch[d];
	}
	return 0;
}
int find_kth(node* o,int k)
{
	if(o==NULL||k>o->s)return -1;
	int s=(o->ch[0]==NULL?0:o->ch[0]->s);
	if(k==s+1)return o->v;
	else if(k<=s) return find_kth(o->ch[0],k);
	else return find_kth(o->ch[1],k-s-1);
}

void solve()
{
	node *root=NULL;
	for(int i=1;i<=n;i++)
		insert(root,i);
	for(int i=0;i<n-1;i++)
		scanf("%d",&ans[i]);
	for(int i=n-2;i>=0;i--){
		//cout<<"ans["<<i<<"]=="<<ans[i]<<endl;
		ans[i]=find_kth(root,ans[i]+1);
		//cout<<"ans["<<i<<"]=="<<ans[i]<<endl;
		remove(root,ans[i]);
	}
	printf("%d\n",root->v);
	for(int i=0;i<=n-2;i++)
		printf("%d\n",ans[i]);
}
int main()
{
	while(~scanf("%d",&n))
		solve();
	return 0;
}
时间: 12-17

Poj 2182-Lost Cows(Treap||树状数组+二分答案)的相关文章

POJ 题目2481 Cows(树状数组)

Cows Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 13920   Accepted: 4607 Description Farmer John's cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in hi

POJ 2481 Cows 简单树状数组区间覆盖

点击打开链接 Cows Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 13334   Accepted: 4413 Description Farmer John's cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line

POJ 2182 Lost Cows.(线段树)

~~~~ 数据太水,暴力无压力,不过还是用线段树写了下,表现了楼主对线段树的无限热爱之情. ~~~~ 题目连接:http://poj.org/problem?id=2182 大致题意;牛牛因XXXXXX原因乱序成一排,现已知每头牛前面有多少头牛比它的编号小(第一头牛前面没有当然就不列粗来了),求每头牛的编号. 思路:从后往前扫描,遇到a,则说明它是剩余序列的第a+1头牛. ~~~~ 暴力代码:(157ms) #include<cstdio> #include<algorithm>

poj 3321:Apple Tree(树状数组,提高题)

Apple Tree Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 18623   Accepted: 5629 Description There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been

POJ 2828 poj 2828 Buy Tickets 【树状数组,已知前n项和为K,返回n值】

题目链接:http://poj.org/problem?id=2828 在一个队列中,一个人想要插队,告诉你每个新来的人会插在i个人后面,求出最后的队列. 如果我们用模拟的话,那么时间复杂度肯定是超了:想想,如果我们逆序,那么最后来的人的位置一定是固定的,这样的话,我们将问题转化成逆序扫描给出数据,插在i个人后面这个数据就变成了在这个人前面需要留出多少个空位.如此我们只需要用树状数组记录前n项总共有多少个空位,每扫描一个数据,就找出能使得他前面正好有i个空位. 这题用树状数组或者线段树都可以,今

POJ 2464 Brownie Points II 树状数组+扫描线

题意奇葩的一笔,本质上就是一个复杂统计,智商低下的我想不出来只好去搜了题解 #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <set> #include <vector> #include <string> #include <queue> #include <deque> #inclu

POJ 2892 Tunnel Warfare (树状数组+二分)

题目大意: 三个操作 D pos  将pos位置摧毁,让它和周围不相连. Q pos 问和pos 相连的有多少个村庄. R 修复最近摧毁的村庄. 思路分析: 树状数组记录这个区间有多少个1. 如果  [s-e] 有e-s+1个1 的话.那么这个区间是相连的. 这样的话,我们就可以用二分的办法求出与某个位置最大相连的数量. 还有这里二分 while(l<=r) { if(满足) { ans=mid; l=mid+1; } else r=mid-1; } #include <cstdio>

POJ 2299 Ultra-QuickSort (离散化+树状数组)

题目链接:POJ 2299 Ultra-QuickSort 求一串序列相邻连个元素交换多少后,是一串上升的序列. 思路:求该串序列的逆序数,数据比较大,要离散化. AC代码: #include<stdio.h> #include<string.h> #include<set> #include<map> #include<algorithm> #define ll __int64 using namespace std; const ll max

POJ 2828 Buy Tickets (线段树 or 树状数组+二分)

题目链接:http://poj.org/problem?id=2828 题意就是给你n个人,然后每个人按顺序插队,问你最终的顺序是怎么样的. 反过来做就很容易了,从最后一个人开始推,最后一个人位置很容易就确定了,那最后第二个人的位置也可以推(与最后一个人的位置无关)...依次就都可以确定所有的人了. 用前缀和的思想,要是这个人的位置确定了,那么就标记这个人位置的值为0,然后回溯更新,跟求逆序对个数的思想比较类似. 线段树: 1 #include <iostream> 2 #include &l