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