无语钢笔

文章
7
资源
0
加入时间
3年12月3天

CF Round#680 D.Divide and Sum

Divide and Sum思维题意:给出一个长度2n的数列,将其划分为两个数列p、q(只要下标不同即视为不同划分),其中p为降序序列、q为增序序列。定义f(p,q)=sum{|p[i]-q[i]|1<=i<=n}。问所有划分的f值总和。思路:首先对2n个数排序,先逐个观察对于其中的a[i] (i<=n),将其放在数列q(增序)中第t个位置q[t],可知q中a[i]右侧的数共(n-t)个都大于等于a[i],由于共有2n-i个数大于a[i],而2*n-i-