好题
图论的难点在于建图~
首先我们关注到如果两个草堆之间的差大于K,那么他们的位置就是固定的,就相当于给了一些限制,这就是很经典的连边然后拓扑排序。其实你是不是可以直接从小的向大的连边(我没试)然后再做排序。
这一部分代码(粗略验证正确性,赶着写的,可能比较一言难尽)
#include<bits/stdc++.h>
using namespace std;
vector<int> tree[100005];
bool vis[100005];
int du[100005],ans[100005],h[100005],n,m;
void tuopu(){
int done=0,now,mini;
while(done<n){
mini=1e9;
for(int i=1;i<=n;++i){
if(!du[i]&&!vis[i]){
if(h[i]<mini) mini=h[i],now=i;
}
}
vis[now]=1;ans[++done]=now;
for(int j=0;j<tree[now].size();++j) --du[tree[now][j]];
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&h[i]);
for(int i=1;i<n;++i){
for(int j=i+1;j<=n;++j){
if(abs(h[i]-h[j])>m) tree[i].push_back(j),++du[j];
}
}
tuopu();
for(int i=1;i<=n;++i) printf("%d\n",h[ans[i]]);
return 0;
}
这样的时间和空间复杂度都是\(\Theta(nK)\)的,无法接受,注意到瓶颈在于K,所以我们对可能存在的边数进行一个优化,我们需要每次取出的信息是入度最小的可能点,然后每次还需要对这个点所可能指向的点的入度进行修改(注意我们是在值域上进行操作),可以发现这是一个区间操作,所以用线段树维护。由于值域是1e9的,所以要离散化。看注释。
代码
#include<bits/stdc++.h>
#define ll long long
#define lb lower_bound
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=1e5+5;
unordered_map<int,int> mp;
int n,K,a[N],h[N],c[N],tree[N],deg[N];
struct Heap{ll d=N;int id;};//度和编号
struct Seg{
int l,r;
ll tag;
Heap val;
}tr[N<<2];
inline Heap min(const Heap A,const Heap B){
if(A.d==B.d)return A.id<B.id?A:B;
else return A.d<B.d?A:B;
}
inline int read(){
char ch;int x=0,f=1;
while(!isdigit(ch=getchar())){if(ch=='-')f=-1;}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}return;
}
inline ll qry(int x){
ll res=0;while(x){
res+=tree[x];
x-=lowbit(x);
}return res;
}
inline void Build(const int p,const int l,const int r){
tr[p].l=l,tr[p].r=r;
if(l==r){
tr[p].val.d=deg[l],tr[p].val.id=l;
return;
}int mid=(l+r)>>1;
Build(ls,l,mid),Build(rs,mid+1,r);
tr[p].val=min(tr[ls].val,tr[rs].val);
}
inline void Change(const int p,const int val){tr[p].val.d+=val,tr[p].tag+=val;}//维护的是最小值所以只单点减
inline void Pushdown(const int p){
if(!tr[p].tag)return;
Change(ls,tr[p].tag),Change(rs,tr[p].tag);
tr[p].tag=0;
}
inline void Mdf(const int p,const int l,const int r,const int val){
if(l>tr[p].r||r<tr[p].l)return;
if(tr[p].l>=l&&tr[p].r<=r){
Change(p,val);return;
}Pushdown(p);
// int mid=(tr[p].l+tr[p].r)>>1;
/*if(l<=mid)*/Mdf(ls,l,r,val);
/*if(mid<r)*/Mdf(rs,l,r,val);//离散化了,所以不能这样写
tr[p].val=min(tr[ls].val,tr[rs].val);
}
int main(){
n=read(),K=read();
for(int i=1;i<=n;++i)c[i]=h[i]=read();
sort(c+1,c+n+1);
for(int i=1;i<=n;++i){
int x=lb(c+1,c+n+1,h[i])-c;
mp[h[i]]++;h[i]=x+mp[h[i]]-1;
}for(int i=1;i<=n;++i){
int x=lb(c+1,c+n+1,c[h[i]]-K)-c-1,y=lb(c+1,c+n+1,c[h[i]]+K+1)-c-1;
deg[h[i]]=i-1+qry(x)-qry(y),add(h[i],1);//x前面的和包含y的后面的都固定,也就是要连边
}Build(1,1,n);//for(int i=1;i<=n;++i)printf("%d ",c[i]);printf("\n");//for(int i=1;i<=n<<2;++i)printf("%d %d %d\n",tr[i].l,tr[i].r,tr[i].val.id);
for(int i=1;i<=n;++i){//这个循环表示取出了几个队头,也就是更新了几个点
int u=tr[1].val.id;//每次取最小的可能为队头,和堆优化dij有相似之处
printf("%d\n",c[u]);
int x=lb(c+1,c+n+1,c[u]-K)-c-1,y=lb(c+1,c+n+1,c[u]+K+1)-c-1;//和上面同理的区间
// printf("%d %d\n%d %d\n%d %d\n%d %d\n%d\n",1,x,y+1,n,u,u,c[u]-K,c[u]+K+1,tr[1].val.d);
Mdf(1,1,x,-1),Mdf(1,y+1,n,-1);//这些地方都有边,所以全部减
Mdf(1,u,u,n);//让这个地方不可能再成为最小
}return 0;
} //topo不局限于具体的图,而是维护deg
标签:const,val,Haybales,int,题解,tr,100005,Minimizing,tag
From: https://www.cnblogs.com/mountzhu/p/18435523