Codeforces 220C
2024-09-01 05:03:59
题意略。
思路:
我们可以把 bi[ i ] 在 ai[ ] 中的位置记录下来,然后算出 i - mp[ bi[i] ] ,再将它压入一个multiset。每次我们就二分地来寻找离0最近的数字来作为答案。
那当我们循环左移的时候怎么办呢?把每个数字都减一,把当前 bi[i] 产生的数字重新赋值再压入吗?
当然不是,我们可以改变0参考系,也即二分地来寻找离i最近的数字来作为答案。(i从0开始,因为第一个答案相当于循环左移0次)
那么要删去的那个数字怎么办呢?
我们将它删去后,压入的值是 (i + n) - mp[ bi[i] ]。可是为什么呢?
可以认为是 参考系的值 + n - mp[ bi[i] ] (原本应该改成的值)。
也可以认为是,当前在multiset中的值其实都已经减去了 i ,为了补上这个i,我要在 n - mp[ bi[i] ] 上加上 i。
详见代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + ; int mp[maxn],bi[maxn],n;
multiset<int> st; int main(){
int n;
scanf("%d",&n);
int temp;
for(int i = ;i < n;++i){
scanf("%d",&temp);
mp[temp] = i;
}
for(int i = ;i < n;++i){
scanf("%d",&bi[i]);
st.insert(i - mp[bi[i]]);
}
for(int i = ;i < n;++i){
multiset<int>::iterator it = st.lower_bound(i);
int ans = maxn;
if(it != st.end()) ans = min(ans,(*it) - i);
if(it != st.begin()) ans = min(ans,i - *(--it));
printf("%d\n",ans);
int t = i - mp[bi[i]];
st.erase(st.find(t));
st.insert((i + n) - mp[bi[i]]);
}
return ;
}
最新文章
- 去IOE的一点反对意见以及其他
- [LeetCode] Rotate List 旋转链表
- jQuery实现选项联动轮播
- PHP入门篇
- mysql 指定端口
- 数字字符与金钱RMB之间的转换
- 贵州大学iPhone、Android(安卓)项目助跑计划!!!
- python练习程序(显示图像)
- PHP中的替代语法
- shell 数组
- Data guard RAC配置【二】
- A Knight&#39;s Journey(dfs)
- A Linear Time Majority Vote Algorithm
- JavaScript之字符串引号的使用技巧
- windows下grunt安装提示不成功
- CSS简介模块
- iOS图片填充UIImageView(contentMode)
- IntelliJ IDEA(2017.2)安装和破解(转)
- CentOS下MySQL的安装
- 浅析Kubernetes的工作原理
热门文章
- Codeforces1144D(D题)Equalize Them All
- visionpro和halcon这两款机器视觉软件区别
- thinkphp phpexcel导出返回乱码
- android 界面提示框架WisdomProgressHUD,为金典而生
- 金蝶K3 V12.2版本,中途启用双计量单位出现错误
- 【译】在 Linux 上不安装 Mono 构建 .NET Framework 类库
- NDK jni mk文件 so文件 巴啦啦 初体验
- Redis总结(八)如何搭建高可用的Redis集群
- Redis进阶应用:Redis+Lua脚本实现复合操作
- 基于tp3.2的腾讯云短信验证码的实现