poj 2828 Buy Tickets 【线段树点更新】
2024-08-30 10:47:56
题目: id=2828" target="_blank">poj 2828 Buy Tickets
题意:有n个人排队,每一个人有一个价值和要插的位置,然后当要插的位置上有人时全部的人向后移动一位当这个插入到这儿,假设没有直接插进去。
分析:分析发现直接插入移动的话花时间太多。我们可不能够用逆向思维。
从后往前来。由于最后一个位置是肯定能确定的,而其它的则插入空的第某个位置。
比方第一组例子:
4
0 77
1 51
1 33
2 69
開始时候位置都为空 编号0 1 2 3
首先从最后一个来2 69
第二个位置空,则能够直接放
然后编号变为0 1 69 2
接着放1 33
编号变为 0 33 69 1
然后放1 51
编号变为0 33 69 51
然后放最后一个0 77
则最后结果为 77 33 69 51
能够发现该怎么搞了。就是直接用线段树来维护区间上的值。然后选择插入对应的位置就可以。
AC代码:
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
typedef long long LL ;
const int N = 220000; struct Node
{
int l,r;
int val,num;
};
Node tree[5*N];
void build(int o,int l,int r)
{
tree[o].l = l,tree[o].r = r;
if(l==r)
{
tree[o].val = 1;
return ;
}
int mid = (l+r)/2;
build(o+o,l,mid);
build(o+o+1,mid+1,r);
tree[o].val = tree[o+o].val + tree[o+o+1].val;
}
void update(int o,int num,int val)
{
//printf("%d %d %d %d\n",o,tree[o].l,tree[o].r,tree[o].val);
if(tree[o].l==tree[o].r)
{
tree[o].num = val;
tree[o].val = 0;
return ;
}
if(tree[o+o].val>=num)
update(o+o,num,val);
else
update(o+o+1,num-tree[o+o].val,val);
tree[o].val = tree[o+o].val + tree[o+o+1].val;
}
vector<int> ans;
void Yougth(int o)
{
if(tree[o].l==tree[o].r)
{
ans.push_back(tree[o].num);
return ;
}
Yougth(o+o);
Yougth(o+o+1);
}
pair <int,int> p[N];
int main()
{
//freopen("Input.txt","r",stdin);
int n;
while(~scanf("%d",&n))
{
build(1,1,n);
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x++;
p[i] = make_pair(x,y);
}
for(int i=n-1;i>=0;i--)
update(1,p[i].first,p[i].second);
Yougth(1);
for(int i=0;i<ans.size();i++)
printf("%d%c",ans[i],i==(ans.size()-1)?'\n':' ');
ans.clear();
}
return 0;
}
最新文章
- underscore源码阅读记录(二)
- request.querystring和request.form、session的区别
- 一个Demo学完Android中所有的服务(转)
- 程序员编程艺术第三十六~三十七章、搜索智能提示suggestion,附近点搜索
- 剑指Offer32 丑数
- C#字符串的常用操作
- MySQL源码 数据结构array
- bzoj4546-codechef XRQRS(可持久化Trie)
- x264 - open gop and closed gop
- VI中的批量替换 (转载)
- POJ 3254 Corn Fields(状态压缩)
- [Go] golang使用github里的imap类库
- ansible资产配置
- var entsMapLocation = {……}函数
- Redis Sentinel 配置文件
- Java代码优化总结(持续更新)
- @ControllerAdvice + @ExceptionHandler 全局处理 Controller 层异常==》记录
- poj-1287 Networking(Prim)
- 关于jquery中prev()和next()的用法
- 在centos7虚拟机上挂载镜像,并设置yum源(包括遇到的问题)
热门文章
- 《零基础入门学习Python》【第一版】视频课后答案第005讲
- python爬虫基础03-requests库
- Verilog学习笔记基本语法篇(六)&#183;&#183;&#183;&#183;&#183;&#183;&#183;&#183; 循环语句
- MIP启发式算法:爬山算法 (Hill climbing)
- Ubuntu 清理卸载残留文件
- C#上位机开发(二)—— Hello,World
- CentOS下配置LVM和RAID
- RHEL6.5上升级OpenSSH7.4p1
- Python常用操作符
- 【工具】Homebrew的安装及使用