D. Restore Permutation

题意:给定n个数a[i],a[ i ]表示在【b[1],b[i-1]】这些数中比 b[i]小的数的和,要你构造这样的b[i]序列

题解:利用树状数组 求比b[i]小的数的和,在从大到小二分枚举最大的一个数x,使得左边小于x的所有数的和小于等于a[i],vis保存记录x即可

#include<iostream>
#include<string.h>
#define ll long long
using namespace std;
ll a[],b[],c[],vis[];
//a[i]保存原始数据,b[i]保存比a[i]小的数的个数,c[i]保存所有比a[i]小的数的和
ll lowbit(ll x)
{
return x&(-x);
} ll getsum(ll x)//求比x小的数的和
{
ll ans=;
while(x>)
{
ans=ans+c[x];
x=x-lowbit(x);
}
return ans;
} void add(ll x,ll y)//更新,对第x个位置的数进行更新,y是更新值
{
while(x<=)
{
b[x]=b[x]+;
c[x]=c[x]+y;
x=x+lowbit(x);
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
ll ans=,sum=;
memset(a,,sizeof(a));
memset(b,,sizeof(b));
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
add(i,i);//将第x个位置的值,修改为x
}
for(int i=n;i>=;i--)
{
ll le=,ri=n,mid;
while(le<ri)//从右往左,二分枚举最大的x,使得左边小于x的所有数的和小于等于a[i]
{
mid=(le+ri+)/;
if(getsum(mid-)<=a[i])
le=mid;
else
ri=mid-;
}
vis[i]=le;
add(le,-le);//枚举到这个数之后就把这个数置为零
}
for(int i=;i<=n;i++)
{
if(i==)
printf("%lld",vis[i]);
else
printf(" %lld",vis[i]);
}
printf("\n");
}
return ;
}

最新文章

  1. ionic 设置logo 与 设置 启动页
  2. shop++ 安装
  3. Mac下启动Apache
  4. [转]Xcode的重构功能
  5. Amazon MWS 上传数据 (一) 设置服务
  6. js获取字符串最后一位方法
  7. Short But Scary 解题报告
  8. Python Django CBV下的通用视图函数
  9. Hibernate HQL一对多 在一方的查询
  10. 求最小生成树的kruskal算法
  11. python进行数据分析
  12. 基于TLS证书手动部署kubernetes集群(下)
  13. REQUIRES_NEW 如果不在一个事务那么自己创建一个事务 如果在一个事务中 自己在这个大事务里面在创建一个子事务 相当于嵌套事务 双层循环那种
  14. mac 设置mysql开机自启动
  15. 使用Dockerfile构建docker lnmp环境
  16. PyQt5教程——布局管理(4)
  17. Eclipse For Android 代码自动提示功能
  18. bzoj 3159: 决战
  19. 20155229实验二 《Java面向对象程序设计》实验报告
  20. div横排放置对齐问题;block,inline,inline-block区别

热门文章

  1. SpringBoot与Shiro整合
  2. windows远程linux的方法(不用xshell)
  3. twisted reactor calllater实现
  4. reduxDevTool 配置
  5. 2019年7月22日A股科创板开板首日行情思考
  6. 杭电 1203 I NEED A OFFER!
  7. Python读取MNIST数据集
  8. 【PAT甲级】1002 A+B for Polynomials (25 分)
  9. java 使用poi 导入Excel 数据到数据库
  10. Wcf托管在IIS中,HttpContext.Current为空