【uoj#180】[UR #12]实验室外的攻防战 结论题+树状数组
2024-08-26 10:24:23
题目描述
给出两个长度为 $n$ 的排列 $A$ 和 $B$ ,如果 $A_i>A_{i+1}$ 则可以交换 $A_i$ 和 $A_{i+1}$ 。问是否能将 $A$ 交换成 $B$ 。
输入
输入数据第一行包含一个正整数 $n$ 。
接下来两行每行 $n$ 个正整数,分别描述排列 $A$ 和排列 $B$ 。
输出
对于每组数据,如果存在这样的指令序列,输出“YES”,否则输出“NO”(引号不输出,请注意大小写)。
样例输入
5
4 1 2 5 3
1 2 4 3 5
样例输出
YES
题解
结论题+树状数组
结论:能将 $A$ 交换成 $B$ 的充要条件为:不存在 $i<j$ 使得 $A_i<A_j$ 且 $B_i>B_j$ 。
证明:简单模拟冒泡排序的过程即可得出结论。
那么我们要判断的就是是否存在 $i<j$ 使得 $A_i<A_j$ 且 $B_i>B_j$。
这看起来是一个三维偏序问题,但实际上我们只需要判断其存在性。因此可以:扫描法处理 $i<j$ ,对于从小到大的每个 $j$ ,找出所有 $A_i<A_j$ 中 $B_i$ 的最大值,看最大值是否大于 $B_j$,然后再加入 $j$ 。
这样就可以仅使用树状数组解决问题,时间复杂度 $O(n\log n)$
#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
int n , a[N] , b[N] , f[N];
inline void add(int x , int a)
{
int i;
for(i = x ; i <= n ; i += i & -i)
f[i] = max(f[i] , a);
}
inline int query(int x)
{
int i , ans = 0;
for(i = x ; i ; i -= i & -i)
ans = max(ans , f[i]);
return ans;
}
int main()
{
int i , x;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , a[x] = i;
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , b[x] = i;
for(i = 1 ; i <= n ; i ++ )
{
if(query(a[i]) > b[i])
{
puts("NO");
return 0;
}
add(a[i] , b[i]);
}
puts("YES");
return 0;
}
最新文章
- AngularJS 中的Promise --- $q服务详解
- size_t 类型
- android开发之自定义组件
- wordpress如何批量关闭旧日志留言功能
- You Only Live Once
- 201. Bitwise AND of Numbers Range
- office2010安装出错,windows installer服务不能更新一个或多个受保护的windows文件
- redhat6.3+oracle11GR2 单库 安装规划
- img标签在div中水平垂直居中--两种实现方式
- callback和spring的MD5加密
- 嵌入式开发之UDP 丢包--- UDP 丢包控制方法
- 2017.11.11 B201 练习题思路及解题方法
- MySQL下查看和赋予权限
- Django实战(3):Django也可以有scaffold
- Hadoop mapreduce自定义排序WritableComparable
- bzoj3545-bzoj3551-Peaks
- php 将二维数组批量插入到数据库中
- cordova添加android平台时选择安装版本: requirements check failed for jdk 1.8
- 新建tomcat的server服务,在左侧项目浏览处,右键空白的地方,选择new,再选择other选项
- 训练指南 UVALive - 5713(最小生成树 + 次小生成树)
热门文章
- 20155339《java程序设计》第一次实验报告
- cogs1713 [POJ2774]很长的信息
- 面向忙碌开发者的 Android
- Unity CombineTexture
- javaweb(十四)——JSP原理
- Python基础灬高阶函数(lambda,filter,map,reduce,zip)
- Material Safety Data Sheet,MSDS - 化学品安全说明书
- Python常用模块之hashlib
- Base64编码图片存取与前台显示
- USACO 3.2.6 Sweet Butter 香甜的黄油(最短路)