【学习笔记】贪心好题！

【学习笔记】贪心好题！

　　这是一篇持续更新的博客。

　　不废话了直接上题吧。

　　1.洛谷 P2512 糖果传递

　　　　有n个小朋友坐成一圈，每人有A_i个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。

　　　　题解：最终结果可以计算，记为S。

　　　　　　　我们假设所有传递都是向左传递（有向右的自然成为负数），设每个人的传递数量是K_i，这样便于统计。

　　　　　　　那么对于第i个小朋友，他最后的糖果数量就是 A_i-K_i+K_i+1。这个数值等于S。

　　　　　　　可以列出n个方程。

　　　　　　　S=A₁-K1+K2 移向得 K2=S-A1+K1。

　　　　　　　S=A2-K2+K3 代换得 K3=S-A2+K2=S-A2+S-A1+K1=2*S-A1-A2+K1。

　　　　　　　依次代换下去，可以得到第n个方程是Kn=n*S-A1-A2-…-An+K1。

　　　　　　　设Ci=Ai-S。

　　　　　　　K2=K1-C1

　　　　　　　K3=K1-C2

　　　　　　　所以我们传递数量的总和就变成了|K1|+|K1-C1|+…+|K1-Cn-1|.

　　　　　　　可以抽象成一个数轴，上面有K1 C1 C2 C3 … Cn-1这n个点。取其中一个点使得所有距离尽可能近。

　　　　　　　答案在中位数取到，于是就可以轻松的AC了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long n,a[1000001],k[1000001],sum,ans;
 4 int main()
 5 {
 6     scanf("%lld",&n);
 7     for(int i=1;i<=n;i++)
 8     {
 9         scanf("%lld",&a[i]);
10         sum+=a[i];
11     }
12     sum/=n;
13     for(int i=1;i<=n;i++)
14     {
15         k[i]=k[i-1]-a[i]+sum;
16     }
17     sort(k+1,k+n+1);
18     int mid=k[(n+1)/2];
19     for(int i=1;i<=n;i++)
20     {
21         ans+=abs(k[i]-mid);
22     }
23     printf("%lld",ans);
24     return 0;
25 }

转载于:.html