邯郸个人网站建设,flask做克隆网站,茶叶网站开发,廊坊关键词排名优化Problem bzoj Luogu 题目大意#xff1a; 给定序列\(\{a_i\}\)#xff0c;求一个严格递增序列\(\{b_i\}\)#xff0c;使得\(\sum \bigl |a_i-b_i\bigr|\)最小 Thought 正序#xff1a;直接对应 逆序#xff1a;取中位数#xff08;证明#xff1a;“医院设置” Luogu 题目大意 给定序列\(\{a_i\}\)求一个严格递增序列\(\{b_i\}\)使得\(\sum \bigl |a_i-b_i\bigr|\)最小 Thought 正序直接对应 逆序取中位数证明“医院设置” 最优解一定是分段 每一段台阶式上升 每一段选取中位数 沙漏型左偏树 合并区间 选取中位数 upd:貌似不需要沙漏型 Solution 前置技能小学奥数、可并堆 和上面类似先不考虑严格上升即先考虑非严格上升 序列一定是要分成若干段每一段的\(b\)值相等且后一段比前一段大像台阶一样如下图是一个\(b(x)\)的伪函数 先令\(\forall i\in[1,n],a_ib_i\)这样的答案为零但却不合法接下来考虑如何用最小代价使答案合法考虑对于相邻两段数 设当前前一段取最优值时的\(b\)统一为\(b_1\)后一段统一为\(b_2\)变换之后两者的统一\(b\)值分别变为\(b_1^{},b_2^{}\) 如果\(b_1\leq b_2\)则对于这两段来说是合法的无需操作 如果\(b_1b_2\)则表示因为要求\(b_1\leq b_2\)而现在是\(b_1b_2\)要求\(b_1^{}\leq b_2^{}\)考虑到两段的\(b\)变化得越少越好即\(\bigl | b_1-b_1^{}\bigr |,\bigl | b_1-b_1^{}\bigr |\)取最小则变换之后\(b_1^{}b_2^{}\)我们再考虑\(b_1^{}(b_2^{})\)的取值应为这两段数合在一起的中位数证明见下方“附”找中位数可以用线段树解决也可以用堆解决堆解法见TJOI2010中位数考虑到两段需要合并线段树需要线段树合并而堆只需要可并堆即可 如何把相邻两段的处理扩展到整个序列呢鉴于整个\(b\)序列是递增的可以用单调栈实现栈中的比较方式就是上述对于相邻两段的处理 现在解除一开始自己设置的限制将\(a_i\)设为\(a_i-i\)即可将非严格上升序列的做法转移到严格上升序列的做法 附证明其实就是小学奥数题 对于一段数\(\{c_i\}\)选取\(x\)使得\(\sum \bigl |x-c_i \bigr |\)最小的\(x\)值的一个取值为\(\{c_i\}\)序列的中位数 反证法设原序列有\(n\)个元素则比\(x\)大/小的数有\(\frac n2\)个若\(x\)变小或变大则若越过序列中另一个值时比\(x\)大/小的数有\(\frac n2±1\)个统计答案时只会增加\(2\)或不变 Code #includebits/stdc.h
using namespace std;
typedef long long ll;
#define rg registerstruct ios {inline char read(){static const int IN_LEN118|1;static char buf[IN_LEN],*s,*t;return (st)(t(sbuf)fread(buf,1,IN_LEN,stdin)),st?-1:*s;}template typename _Tp inline ios operator (_Tpx){static char c11,boo;for(c11read(),boo0;!isdigit(c11);c11read()){if(c11-1)return *this;boo|c11-;}for(x0;isdigit(c11);c11read())xx*10(c11^0);boo(x-x);return *this;}
} io;const int N1001000;
struct Leftist_Tree{int l,r,dis,val;}t[N];
struct node{int l,r,rt,sz,val;node(){}node(const intL,const intid){lL,rrtid,sz1,valt[id].val;}
}h[N];
int n,top;inline int merge(int u,int v){if(!u||!v)return u|v;if(t[u].valt[v].val||(t[u].valt[v].valuv))swap(u,v);intlt[u].l,rt[u].r;rmerge(r,v);if(t[l].dist[r].dis)swap(l,r);t[u].dist[r].dis1;return u;
}inline int del(int u){return merge(t[u].l,t[u].r);}void work(){ion;for(rg int i1;in;i)iot[i].val,t[i].val-i;h[top1]node(1,1);for(rg int i2;in;i){int lh[top].r1;h[top]node(l,i);while(top^1h[top-1].valh[top].val){--top;h[top].rtmerge(h[top].rt,h[top1].rt);h[top].rh[top1].r;h[top].szh[top1].sz;while(h[top].sz((h[top].r-h[top].l2)1)){--h[top].sz;h[top].rtdel(h[top].rt);}h[top].valt[h[top].rt].val;}}return ;
}void Print(){ll Ans0;for(rg int i1,p1;in;i){if(ih[p].r)p;Ansabs(h[p].val-t[i].val);}printf(%lld\n,Ans);for(rg int i1,p1;in;i){if(ih[p].r)p;printf(%d ,h[p].vali);}putchar(\n);return ;
}int main(){work();Print();return 0;
} 转载于:https://www.cnblogs.com/penth/p/9239977.html
