[USACO22JAN] Minimizing Haybales P
随机化?五分。
显然对于任意 \(a_i,a_j\),若 \(|a_i-a_j|>K\),则这两堆草的先后顺序永远不会改变。所以易得暴力:对于所有这样的 \(i,j\),不妨设 \(i<j\),则连一条 \(i\to j\) 的边,答案就是这个图字典序最小的拓扑排序,优先队列即可。
void toposort(){
priority_queue<pair<int,int>>q;
for(int i=1;i<=n;++i) if(!in[i]) q.emplace(-h[i],i);
while(!q.empty()){
int u=q.top().second;
q.pop();
write(h[u]);
for(int i=head[u];i;i=e[i].to)
if(--in[e[i].v]==0)
q.emplace(-h[e[i].v],e[i].v);
}
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;++i) h[i]=read();
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(abs(h[i]-h[j])>k)
addedge(i,j),++in[j];
toposort();
return fw,0;
}
考虑优化,发现复杂度瓶颈在于连边。正常拓扑排序的操作为:将所有入度为零的点入队,每次删掉当前点。那么神奇地,对于暴力的每一步我们都想办法优化:
- 如何求初始的入度?将原数组离散化,二分找到所有和当前点相差超过 \(K\) 的点,点数就是入度。然后把这些点加入线段树,就完成了入队的操作。
- 如何维护全局最小值?线段树啊。
- 如何删点?还是二分找到所有和当前点相差超过 \(K\) 的节点,将这些点的入度 \(-1\),然后给当前点的入度 \(+\infty\),就完成了删点的操作。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=1e5+5;
int n,k,h[MAXN],b[MAXN],tot;
int deg[MAXN];
unordered_map<int,bool>vis;
struct{
#define lp p<<1
#define rp p<<1|1
#define mid ((s+t)>>1)
pair<int,int>st[MAXN<<2];
int lazy[MAXN<<2];
void build(int s,int t,int p){
if(s==t){
st[p]={deg[s],s};
return;
}
build(s,mid,lp),build(mid+1,t,rp);
st[p]=min(st[lp],st[rp]);
}
void pushdown(int p){
if(!lazy[p]) return;
st[lp].first+=lazy[p];
st[rp].first+=lazy[p];
lazy[lp]+=lazy[p];
lazy[rp]+=lazy[p];
lazy[p]=0;
}
void mdf(int l,int r,int k,int s=1,int t=n,int p=1){
if(l>r) return;
if(l<=s&&t<=r) return st[p].first+=k,lazy[p]+=k,void();
pushdown(p);
if(l<=mid) mdf(l,r,k,s,mid,lp);
if(mid<r) mdf(l,r,k,mid+1,t,rp);
st[p]=min(st[lp],st[rp]);
}
#undef mid
}T;
struct{
#define lowbit(x) (x&-x)
int c[MAXN];
void add(int x,int k){
while(x<=n) c[x]+=k,x+=lowbit(x);
}
int sum(int x){
int res=0;
while(x) res+=c[x],x-=lowbit(x);
return res;
}
}B;
int main(){
n=read(),k=read();
for(int i=1;i<=n;++i) h[i]=b[i]=read();
sort(b+1,b+n+1);tot=n;
for(int i=1;i<=n;++i)
h[i]=lower_bound(b+1,b+tot+1,h[i])-b+vis[h[i]]++;
for(int i=1;i<=n;++i){
int x=lower_bound(b+1,b+tot+1,b[h[i]]-k)-b-1;
int y=lower_bound(b+1,b+tot+1,b[h[i]]+k+1)-b-1;
deg[h[i]]=i-1+B.sum(x)-B.sum(y);
B.add(h[i],1);
}
T.build(1,n,1);
for(int i=1;i<=n;++i){
int sh=T.st[1].second;
write(b[sh]);
int x=lower_bound(b+1,b+tot+1,b[sh]-k)-b-1;
int y=lower_bound(b+1,b+tot+1,b[sh]+k+1)-b-1;
T.mdf(1,x,-1);
T.mdf(y+1,n,-1);
T.mdf(sh,sh,1e9);
}
return fw,0;
}
标签:USACO22JAN,Haybales,题解,入度,入队,Minimizing,define
From: https://www.cnblogs.com/laoshan-plus/p/18530720