题目大意

给你一个序列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 ;
}

最新文章

  1. vmware centos nat模式下连不上网络解决办法
  2. C语言 Linux内核链表(企业级链表)
  3. Provider 错误 &#39;80004005&#39; 未指定的错误 /conn.asp,行 23
  4. Java 数组 可变长参数 实例
  5. Openjudge计算概论-单词翻转
  6. SQL Server 修复数据库 相关 脚本 之 DBCC CHECKDB 用法 来自同事分享
  7. es6新特性:
  8. SQL事务与并发
  9. QF——OC内存管理详解
  10. Linux之shell编程基础
  11. decimal ? 含义
  12. POJ3061 Subsequence(二进制前缀和法律+仿真足)
  13. Android应用的基本组件介绍和签名Android应用程序
  14. scan函数用法详解
  15. Java面试题详解四:==和equals的去别
  16. springmvc搭配nginx 实现动静分离
  17. ext.js的mvc开发模式详解
  18. MySQL事务(三)
  19. LInux查看网速带宽及各进程占用情况:nethogs
  20. 给文件夹添加Everyone用户

热门文章

  1. vue 上传文件 并以表格形式显示在页面上
  2. flume 进阶
  3. Redis基础都不会,好意思出去面试?
  4. [BZOJ 2989]数列(CDQ 分治+曼哈顿距离与切比雪夫距离的转化)
  5. Codeforces 840C 题解(DP+组合数学)
  6. ES6精解:变量的解构赋值
  7. Photoshop制作Android UI:怎样从大图片中准确剪切出圆角正方形 图片
  8. 逐行读取txt文件,分割,写入txt。。。上传,下载
  9. 2019-3-9-通过-frp-开启服务器打开本地的-ZeroNet-服务器外网访问
  10. postgres - 以单用户模式运行一个 PostgreSQL服务器