1208D Restore Permutation
2024-09-06 00:05:25
题目大意
给你一个序列s
让你求一个1~n的序列
使得对于第i个位置它前面所有小于p[i]的数的和恰好为s[i]
分析
我们可以从后往前确定每一位
每次一二分找到恰好等于s[i]的数
但是我们发现这样会产生重复选一个点的情况
所以我们改为每次找第一个大于s[i]的点
这个点-1恰好为答案
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
int d[],n,s[],a[];
inline int lb(int x){return x&(-x);}
inline void add(int x,int k){while(x<=n)d[x]+=k,x+=lb(x);}
inline int q(int x){int res=;while(x)res+=d[x],x-=lb(x);return res;}
signed main(){
int i,j,k;
scanf("%lld",&n);
for(i=;i<=n;i++)scanf("%lld",&s[i]);
for(i=;i<=n;i++)add(i,i);
for(i=n;i>;i--){
int le=,ri=n,ans;
while(ri-le>){
int mid=(le+ri)>>;
if(q(mid)<=s[i])le=mid;
else ri=mid;
}
a[i]=ri;
add(a[i],-a[i]);
}
for(i=;i<=n;i++)printf("%lld ",a[i]);
puts("");
return ;
}
最新文章
- vmware centos nat模式下连不上网络解决办法
- C语言 Linux内核链表(企业级链表)
- Provider 错误 &#39;80004005&#39; 未指定的错误 /conn.asp,行 23
- Java 数组 可变长参数 实例
- Openjudge计算概论-单词翻转
- SQL Server 修复数据库 相关 脚本 之 DBCC CHECKDB 用法 来自同事分享
- es6新特性:
- SQL事务与并发
- QF——OC内存管理详解
- Linux之shell编程基础
- decimal ? 含义
- POJ3061 Subsequence(二进制前缀和法律+仿真足)
- Android应用的基本组件介绍和签名Android应用程序
- scan函数用法详解
- Java面试题详解四:==和equals的去别
- springmvc搭配nginx 实现动静分离
- ext.js的mvc开发模式详解
- MySQL事务(三)
- LInux查看网速带宽及各进程占用情况:nethogs
- 给文件夹添加Everyone用户
热门文章
- vue 上传文件 并以表格形式显示在页面上
- flume 进阶
- Redis基础都不会,好意思出去面试?
- [BZOJ 2989]数列(CDQ 分治+曼哈顿距离与切比雪夫距离的转化)
- Codeforces 840C 题解(DP+组合数学)
- ES6精解:变量的解构赋值
- Photoshop制作Android UI:怎样从大图片中准确剪切出圆角正方形 图片
- 逐行读取txt文件,分割,写入txt。。。上传,下载
- 2019-3-9-通过-frp-开启服务器打开本地的-ZeroNet-服务器外网访问
- postgres - 以单用户模式运行一个 PostgreSQL服务器