建设区服务网站,最大的中文搜索引擎,推广费用怎么算,花卉网站建设推广正题
题目链接:https://www.luogu.com.cn/problem/P4331 题目大意
给出一个序列aaa#xff0c;求一个单调上升的序列bbb使得∑i1n∣ai−bi∣\sum_{i1}^n|a_i-b_i|∑i1n∣ai−bi∣最小。 解题思路
巧妙的解法
首先我们让所有的ai−ia_i-iai−i这样我们求的bbb序列就…正题
题目链接:https://www.luogu.com.cn/problem/P4331 题目大意
给出一个序列aaa求一个单调上升的序列bbb使得∑i1n∣ai−bi∣\sum_{i1}^n|a_i-b_i|∑i1n∣ai−bi∣最小。 解题思路
巧妙的解法
首先我们让所有的ai−ia_i-iai−i这样我们求的bbb序列就只需要满足单调不降。
然后考虑特殊情况
对于一串连续的满足ax≤ax1a_x\leq a_{x1}ax≤ax1那么这一段的bxaxb_xa_xbxax对于一串连续的满足ax≥ax1a_x\geq a_{x1}ax≥ax1那么这一段的bxb_xbx为这一段数的中位数
而且对于连续的两个区间(L,mid)(L,mid)(L,mid)和(mid1,R)(mid1,R)(mid1,R)的局部最优解也满足一下性质所以就有做法
我们维护若干段局部最优解www每次加入一个数aia_iai如果满足ai≥wcnta_i\geq w_{cnt}ai≥wcnt那么有biaib_ia_ibiai。如果ai≤wcnta_i\leq w_{cnt}ai≤wcnt那么我们就将aia_iai合并入前面的局部最优解并重新计算这一段的中位数后继续看是否需要与前面合并即判断是否wcnt≥wcnt−1w_{cnt}\geq w_{cnt-1}wcnt≥wcnt−1。
我们可以左偏树做到动态合并和维护中位数保持堆中个数为一半即可。时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
int n,cnt,a[N],rt[N],L[N],R[N];
int t[N][2],dis[N],val[N],siz[N];
long long ans;
int Merge(int x,int y){if(!x||!y)return xy;if(val[x]val[y])swap(x,y);int lst[x][0],rst[x][1];rsMerge(rs,y);if(dis[ls]dis[rs])swap(ls,rs);dis[x]dis[ls]1;return x;
}
void Pop(int x)
{siz[x]--;rt[x]Merge(t[rt[x]][0],t[rt[x]][1]);}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]),a[i]-i;for(int i1;in;i){siz[cnt]1;val[i]a[i];rt[cnt]i;L[cnt]R[cnt]i;while(cnt1val[rt[cnt-1]]val[rt[cnt]]){cnt--;siz[cnt]siz[cnt1];R[cnt]R[cnt1];rt[cnt]Merge(rt[cnt],rt[cnt1]);while(siz[cnt](R[cnt]-L[cnt])/21)Pop(cnt);}}for(int i1;icnt;i)for(int jL[i];jR[i];j)ansabs(a[j]-val[rt[i]]);printf(%lld\n,ans);for(int i1;icnt;i)for(int jL[i];jR[i];j)printf(%d ,val[rt[i]]j);
}
