贪心算法真是令人头疼的一个模块啊,考场上怎么想都想不出来,代码却常常很短……

仓库选址

描述
在一条数轴上有N家商店，它们的坐标分别为 A[1]-A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行一个整数N，第二行N个整数A[1]-A[N]。
输出格式
一个整数，表示距离之和的最小值。
样例输入
4
6 2 9 1
样例输出
12
数据范围与约定
对于100%的数据: N<=100000, A[i]<=1000000

这道题的答案其实就是所有点距离的中位数
我们来证明一下
假设我们所有点中距离中位数的点是k
那么答案就是$\sum_{i=1}^n(a[i]-a[k])$
假设有另外一个点比它更优，这个点为q
那么我们一定可以通过平移点k来得到点q
假如我们平移U点，U点左边有left个点，右边有right个点,那么右移后新的答案会加left乘平移距离，减right乘平移距离，左移后新的答案会加right乘平移距离，减left乘平移距离
若需将k左移则必定有left>right那么必定k点比q点更优，右移同理
综上，答案就是所有点距离的中位数

均分纸牌

题目描述 Description
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。
　　移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
　　现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
　　例如 N=4，4 堆纸牌数分别为：
　　①　9　②　8　③　17　④　6
　　移动3次可达到目的：
　　从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。
输入描述 Input Description
第一行N（N 堆纸牌，1 <= N <= 100）
第二行A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
输出描述 Output Description
输出至屏幕。格式为：
所有堆均达到相等时的最少移动次数。
样例输入 Sample Input
4
9 8 17 6
样例输出 Sample Output
3

首先我们可以看出，如果所有纸牌数量加起来的和除以人数不是整数的话，此题无解
所以均分纸牌后，每个人手里都有纸牌数的平均数个纸牌。
那么我们只需要从第一个人开始依次向后面递推模拟即可

如果下一个人的纸牌数量比平均数多，那么就从当前人向下一个人移动纸牌
如果当前的的人的纸牌数量比平均数少，就从下一个人手里取走纸牌
按此规则进行模拟即可

用s数组存纸牌数量的前缀和
这时我们发现其实答案就是$\sum_{i=1}^nabs(s[i]-i*平均数)$
显然我们在模拟到k个的时候前面k-1个都已经均分好了，只需处理第k个，按照规则进行转移即可
那这样我们发现一个等价做法，我们可以在前缀和之前就将纸牌数量都减少平均数个
显然a数组现在表示纸牌与其他纸牌堆的差值
再把处理后的a数组前缀和的绝对值加起来即可
之所以前缀和是因为前面的纸牌的移动会对后面造成影响

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n;
int a[500050],s[500050];
int abs(int x)
{
    return x>0?x:-x;
}
int main()
{
    scanf("%d",&n);
    int zws=0;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),zws+=a[i];
    zws/=n;
    int answer=0;
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i],answer+=i*zws!=s[i]?1:0;
    printf("%d",answer);
    return 0;
}

环形均分纸牌

题目描述
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
输入格式
小朋友个数n 下面n行 ai
输出格式
求使所有人获得均等糖果的最小代价。
输入输出样例
输入
4
1
2
5
4
输出
4

我们考虑环形均分纸牌可以进行破环成链，那么一个环就有环上点个数种情况(可以从任意点断开)
用a表示减去平均数之后的纸牌数量，s表示对a的前缀和
假设从k处断开，那么这个环就断成了一条链
…………………………
a[k+1] s[k+1]-s[k]
a[k+2] s[k+2]-s[k]
…………………………
a[n] s[n]-s[k]
a[1] s[1]+s[n]-s[k]
…………………………
a[k] s[k]+s[n]-s[k]
因为此处a数组已经减去平均数了，所以s[n]=0
也就是说，答案是$\sum_{i=1}^n(s[i]-s[k])$
此时我们只要找到最小的k就可以了，我们发现现在的情况和前面提到的货仓选址问题一模一样
所以k就是s数组的中位数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
ll n;
ll a[5000050],s[5000050];
ll abss(ll x)
{
    if(x>0)return x;
    else return -x;
}
int main()
{
    scanf("%d",&n);
    ll pjs=0;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),pjs+=a[i];
    pjs/=n;
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]-pjs;
    sort(s+1,s+n+1);
    int k=n/2;
    ll answer=0;
    for(int i=1;i<=n;i++)answer+=abss(s[i]-s[k]);
    printf("%lld",answer);
    return 0;
}