UVA11300 Spreading the Wealth 数学

前方数学警告 题目链接:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2275

https://www.luogu.com.cn/problem/UVA11300

分析:

搞了这么久终于碰到一个数学题了,这也是本蒟蒻做的第一个数学题吧,值得纪念。
第一次看见这题的时候,嗯,好像是个暴力。。。然后就打了一个暴力,发现样例过了?但自己造了组数据就有了点问题,我暴力的思路是由于一个人只能给左边或右边,于是把这两种情况都枚举一下,取最小值就好,但有可能跑一遍不能让整个数组都变成我想要的那个值,故我又加了一个bool表示有无把所有数字都变成那个数,这么写肯定T啊。
我:万一数据水呢?
数据:我不水。
所以交上去果断T掉了,我又想验证一下这么写可不可以,找某人代码过来对拍了一下,然后结果是我竟然把一个A掉的代码给拍出了错解?嗯,看来写个暴力还是有收获的,我其实很想把那个代码粘上来的,但它88行有点长我没存不小心弄丢了,来看一下正解吧。

首先我最开始发现的那个性质是没有问题的,即每个人只会被它周围的人影响,一旦他周围的人的转移硬币数确定了,那么这个人的转移硬币数也可求,于是受这一点启发,不妨设\(x_i\)表示第\(i\)个人给第\(i-1\)个人的硬币数,当\(i==1\)时,为给\(n\)的硬币数。由于最后要求所有人金币一样(共产主义),所以最后每个人的金币数量是确定的,即\(M=tot/n\),也就是说每个人最后都是\(M\),于是有\(A_i+x_{i+1}-x_i=M\),就是原来有的加上得到的减去失去的等于最终的,光看这个式子,这啥也看不出来啊,所以继续观察这个式子,发现它跟周围的式子相加会出现一个神奇的结果,我们加一下看看。
\(A_1+x_2-x_1=M\) 1
\(A_2+x_3-x_2=M\) 2
\(A_3+x_4-x_2=M\) 3
1+2得\(A_1+A_2+x_3-x_1=M*2\) -> \(x_3=x_1-(A_1+A_2-M*2)\)
1+2+3得\(x_4=x_1-(A_1+A_2+A_3-M*3)\)
………………
不难归纳得出\(x_n=x_1-\)\(\sum_{i=1}^n(A_{i-1}+(i-1)*M\)\()\)
有这个式子我们就可以很简单困难的求出答案了,设\(B_i=\)\(\sum_{i=1}^n(A_{i-1}+(i-1)*M\)\(B\)数组可以由递推得到,那么问题就简化成了在数组\(B\)中求一个数,使得剩余数到它的距离之和最小,答案是中位数,证明如下。

UVA11300 Spreading the Wealth 数学


假设\(a_1,a_2,a_3,a_4,a_5\)有序,则\(a_3\)是中位数无疑,我们用线段来表示点与点之间的距离,可以看出蓝色框框内的线段是必不可少的,不管怎么划分都必须要有,如果这个点在\(a_3\)的左边,那么就会多出粉色的一截,在右边就会多出红色的一截,所以在中位数时是最小的。
那偶数呢?偶数不是有两个中位数吗?偶数时也画出一个这样的图,会发现当点在两个中位数之间距离都是一样的,并且是最小,所以为了方便,每次中位数都取\(n+1>>1\)就可以了。

中位数怎么找呢,排序一遍可以,但复杂度是\(O(nlogn)\)的,如果要使数组有序,那么肯定是要\(sort\)的,这里只求中位数,所以可以用\(nth_element\),这个函数的用法是\(nth_element(A+a,b,A+c)\),表示将数组A的区间\([a,c)\)中第b大的数放在b位置上,不保证数组有序,但比这个数大的都在它前边,比它小的在它后边,平均时间复杂度\(O(n)\)

#include<iostream> #include<cmath> #include<algorithm> #define ll long long using namespace std; const int N=1e6+10; ll a[N],b[N]; int main(){ ios::sync_with_stdio(false); int n; while(cin>>n){ ll tot=0; for(int i=1;i<=n;i++) cin>>a[i],tot+=a[i],b[i]=0; tot/=n; for(int i=2;i<=n;i++) b[i]=b[i-1]+a[i]-tot; int mid=n+1>>1; nth_element(b+1,b+mid,b+n+1); ll temp=b[mid],res=0; for(int i=1;i<=n;i++) res+=abs(temp-b[i]); cout<<res<<'\n'; } }

tips:cout<<endl的确比cout<<'\n'慢一点。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwzjys.html