一些有关贪心的题目，证明相当有难度，值得反复推敲！

上课睡觉

题目

原题链接

有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。

你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。

我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。

请你输出所需的最少操作次数。

本题一定有解，因为可以将所有石子堆合并为一堆。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N。

第二行包含 N 个整数 a1,a2,…,aN。

输出格式
每组数据输出一行结果。

数据范围
1 ≤ T ≤ 10,
1 ≤ N ≤ 10^5,
0 ≤ ai ≤ 10^6,
ai求和 ≤ 106,
每个输入所有 N 之和不超过 10^5。

输入样例：

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

输出样例：

3
2
0

样例解释
第一组数据，只需要用 3 个操作来完成：

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

第二组数据，只需要用 2 个操作来完成：

   2 2 3
-> 2 5
-> 7

第三组数据，我们什么都不需要做。

分析

这题有两个未知信息，一个是每堆石子数量和合并次数，我们不妨设它们为x和y，于是我们可以得到等式x * (n - y) = 石子总数，我们会发现x和y是成正比的，故找到最小的合并次数，可以转化为找到最小的每堆石子数量，为此我们枚举每堆石子的数量即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int T,n;
int a[N];
LL sum,maxv;
//能否分成每堆t个
bool check(LL t)
{
    LL cur = 0;
    for(int i = 0;i < n;i++)
    {
        cur += a[i];
        if(cur == t) cur = 0;
        else if(cur > t) return false;
    }
    return true;
}
int main()
{
    cin >> T;
    while(T--)
    {
        sum = 0,maxv = 0;
        cin >> n;
        for(int i = 0;i < n;i++)
        {
            cin >> a[i];
            sum += a[i];
            maxv = max(maxv,a[i] * 1ll);
        }
        if(maxv == 0)
        {
            //已经分好了
            cout << "0" << endl;
            continue;
        }
        for(LL i = maxv;i <= sum;i++)
        {
            if(sum % i == 0 && check(i))
            {
                cout << n - (sum / i) << endl;
                break;
            }
        }
    }
}

---

付账问题

题目

原题链接

几个人一起出去吃饭是常有的事。

但在结帐的时候，常常会出现一些争执。

现在有 n 个人出去吃饭，他们总共消费了 S 元。

其中第 i 个人带了 ai 元。

幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。

这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。

你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。

形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

输入格式
第一行包含两个整数 n、S；

第二行包含 n 个非负整数 a1, …, an。

输出格式
输出最小的标准差，四舍五入保留 4 位小数。

数据范围
1 ≤ n ≤ 5×10^5,
0≤ ai ≤ 10^9,
0≤ S ≤ 10^15。

输入样例1：

5 2333
666 666 666 666 666

输出样例1：

0.0000

输入样例2：

10 30
2 1 4 7 4 8 3 6 4 7

输出样例2：

0.7928

分析

这题要求标准差最小，并且给出了公式。我们直接从公式出发即可，题意中均值就是(所付金额 / 总人数)，再将标准差具体化即可。

</div>
根据均值不等式我们可以发现，当每个人所持金额大于S / n时，取S / n时能够让均值不等式取等，即使得标准差最小。但这是一道实际问题，有些人的所持金额可能不足S / n，此时就不满足均值不等式取等条件了。那么我们不妨将这部分人分开考虑，让这部分人付所有所持金额,不足部分让满足条件的人来分摊。假定这部分人总的不足部分为T,相当于让满足条件的人在需付金额 = S - T的条件下用均值不等式。
然后我们排序处理，对这两部分人分别处理，就不难写出以下代码了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long double LD;
const int N = 5e5 + 10;
int n;
LD S;
int a[N];
int main()
{
    cin >> n >> S;
    //决策：让所有b取S / n，即均值不等式取等条件
    for(int i = 0;i < n;i++) cin >> a[i];
    //让a分为两段，前半段取不到S / n，取a为最小。后半段用均值不等式。
    sort(a,a + n);
    LD res = 0,avg = S / n;
    for(int i = 0;i < n;i++)
    {
        //满足条件的这部分人，所付金额为(S - T) / n
        LD cur = S / (n - i);
        //所付金额不够 S / n，付出全部
        if(a[i] < cur) cur = a[i];
        res += (cur - avg) * (cur - avg);
        //分摊所付金额不够这部分人的钱
        S -= cur;
    }
    printf("%.4Lf\n",sqrt(res / n));
    return 0;
}

---

乘积最大

题目

原题链接

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

输出格式
输出一个整数，表示答案。

数据范围
1 ≤ K ≤ N ≤ 10^5,
−10^5 ≤ Ai ≤ 10^5

输入样例1：

5 3
-100000
-10000
2
100000
10000

输出样例1：

999100009

输入样例2：

5 3
-100000
-100000
-2
-100000
-100000

输出样例2：

-999999829

分析

这题的贪心策略并不复杂，主要是能否找到一种较为好写的分类方式。

</div>
根据图中的方式分类，我们甚至可以将k为奇数转化为偶数时的情况，只需要先取一个最大的数即可。
k为偶数的策略为：负数成对取，且从左侧取；正数从右侧取，类似一个归并排序的过程。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10,mod = 1000000009;
int n,k;
int a[N];
int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> a[i];
    sort(a,a + n);
    LL res = 1;
    int l = 0,r = n - 1,sign = 1;
    if(k % 2)
    {
        //k为奇数,先取最右侧的数,之后转化为k-1偶数的问题
        res = a[r--];
        k--;
        //如果所有数均为负数,取数规则相反
        if(res < 0) sign = -1;
    }
    while(k)
    {
        LL lv = (LL)a[l] * a[l + 1],rv = (LL)a[r] * a[r - 1];
        if(lv * sign > rv * sign)
        {
            res = lv % mod * res % mod;
            l += 2;
        }else
        {
            res = rv % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }
    
    cout << res << endl;
    return 0;
}

---

后缀表达式

题目

原题链接

给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 123+−，则 “23+1−” 这个后缀表达式结果是 4，是最大的。

输入格式
第一行包含两个整数 N 和 M。

第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。

输出格式
输出一个整数，代表答案。

数据范围
0 ≤ N,M ≤ 10^5,
−10^9 ≤ Ai ≤ 10^9

输入样例：

1 1
1 2 3

输出样例：

4

分析

这题的看似策略十分简单，尽可能加上正数，减去负数。实际上减号不止可以凑出m个，因为后缀表达式指定数运算顺序相当于中缀表达式加括号，如果能想到m ≠ 0时，能够凑出1 ~ n + m任意个减号，相当于所有数都可以尽可能取正，这题就迎刃而解了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n,m;
int a[N];
int main()
{
    cin >> n >> m;
    for(int i = 0;i < n + m + 1;i++) cin >> a[i];
    sort(a,a + n + m + 1);
    LL res = 0;
    if(m == 0)
    {
        //如果没有负号，就是全部想加
        for(int i = 0;i < n + m + 1;i++) res += a[i];
    }else
    {
        //如果存在负号，则可以最多可以凑出1~(n+m)个负号
        res = a[n + m] - a[0];
        for(int i = 1;i < n + m;i++) res += abs(a[i]);
    }
    cout << res << endl;
    return 0;
}

---

灵能传输

题目

原题链接

在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。

经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位。

你控制着 n 名高阶圣堂武士，方便起见标为 1,2,⋅⋅⋅,n。

每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少（ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态）。

现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i∈[2,n−1]，若 ai≥0 则其两旁的高阶圣堂武士，也就是 i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai<0 则其两旁的高阶圣堂武士，也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。

形式化来讲就是 ai−1+=ai,ai+1+=ai,ai−=2ai。

灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 maxni=1|ai|，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。

输入格式
本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。

接下来依次输入每一组询问。

每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。

接下来一行包含 n 个数 a1,a2,⋅⋅⋅,an。

输出格式
输出 T 行。

每行一个整数依次表示每组询问的答案。

数据范围
1 ≤ T ≤ 3,3≤ n ≤ 300000,|ai|≤ 10^9,
每个评测用例的限制如下：

输入样例1：

3
3
5 -2 3
4
0 0 0 0
3
1 2 3

输出样例1：

3
0
3

输入样例2：

3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1

输出样例2：

5
7
4

样例解释
样例一
对于第一组询问：
对 2 号高阶圣堂武士进行传输操作后 a1=3，a2=2，a3=1。答案为 3。
对于第二组询问：
这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。

分析

这题思维很具有跳跃性，很难想到。需要把题目中的灵能传输过程转化为前缀和来考虑，灵能传输相当于交换前缀和的Si-1和Si，而答案要求Si - Si-1尽可能的小，在图上表示就是要求S0到Sn的图像尽可能平滑。

</div>
那么只有将S数组排序，才能使得图像尽可能平滑。那么如何让排序后,S0到Sn这个过程尽可能少跨度呢?，这里的贪心策略是：让S0先跳到前缀和最小值，再跳到前缀和最大值，最后跳到Sn，其中需要隔一格跳一次。
隔一格跳一次应该是这题贪心的精髓部分，由于我们跳的过程中，必然会有回跳的过程，相比相邻跳，隔一格跳能使回跳时候的Si - Si-1差值不会太大。
在前缀和的基础上再结合贪心，才有了以下代码，可见这题的难度非常高。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int T,n;
LL a[N],s[N];
//标记是否走过
bool st[N];
int main()
{
    cin >> T;
    while(T--)
    {
        cin >> n;
        s[0] = 0;
        for(int i = 1;i <= n;i++)
        {
            cin >> a[i];
            s[i] = s[i - 1] + a[i];
        }
        LL s0 = s[0],sn = s[n];
        if(s0 > sn) swap(s0,sn);
        //灵能传输相当于交换前缀和si-1和si，这一步非常关键
        sort(s,s + n + 1);
        for(int i = 0;i <= n;i++)
        {
            if(s[i] == s0)
            {
                s0 = i;
                break;
            }
        }
        for(int i = n;i >= 0;i--)
        {
            if(s[i] == sn)
            {
                sn = i;
                break;
            }
        }
        memset(st,0,sizeof st);
        //排序后从s0跳到sn,使得路线尽可能平滑
        //这里每隔一个跳，为了方便跳回来
        int l = 0,r = n;
        //从s0跳到最小值
        for(int i = s0;i >= 0;i -= 2)
        {
            a[l++] = s[i];
            st[i] = true;
        }
        //从最大值跳到sn
        for(int i = sn;i <= n;i += 2)
        {
            a[r--] = s[i];
            st[i] = true;
        }
        //从最小值跳回最大值
        for(int i = 0;i <= n;i++)
        {
            if(!st[i]) a[l++] = s[i];
        }
        LL res = 0;
        for(int i = 1;i <= n;i++) res = max(res,abs(a[i] - a[i - 1]));
        cout << res << endl;
    }
    return 0;
}