更好的阅读体验：https://adventurer-w.com/2022/03/10/gready2/

付账问题 九届Java A T10

题意：现在有 n 个人出去吃饭，他们总共消费了 S 元。其中第 i 个人带了 ai 元。寻找一种付款方式使得标准差最小，输出这个标准差。

思考：带的钱ai小于平均值的话，必须付满ai元，剩下带的钱多余平均值的人，去除前面钱不够的人后，又有了新的平均值，再这样计算即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;
LL n,s,a[500010];
int main(){
    cin>>n>>s;

    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a,a+n);

    long double ave = s * 1.0 / n, cur_ave = ave, sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] <= cur_ave)
        {
            s -= a[i];
            sum += (ave - a[i]) * (ave - a[i]);
            cur_ave = s * 1.0 / (n - i - 1);//  当前平均值
        }else sum += (cur_ave - ave) * (cur_ave - ave);
    }
    printf("%.4Lf", sqrt(sum / n));
    return 0;
}

技巧总结：怎样写代码也是一个难点

乘积最大 第九届C++ B T10

题意：给定N个数，求从中选K个数的最大值

思考：

k==n时只有全选。

此外k 如果是偶数的话,选出来的结果一定是非负数 , 原因如下:

• 负数的个数是偶数个的话,负负得正,那么一定是非负数

• 负数的个数如果是奇数个的话,那么我们就只选偶数个绝对值最大的负数

k 如果是奇数个的话：

• 所有的数字如果都是负数,那么选出来的结果也一定都是负数
• 否则的话,则一定至少有 1个非负数, 那么我们将最大的非负数取出来, 此时要选的个数就是 k-1, k-1 是偶数,那么就又转化为 k– 是偶数的情况思考

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;
const int mod=1000000009;
int n,k,a[100010];
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    LL res=1;
    int l=0,r = n-1;
    int sign = 1 ;

    if(k%2){   //只要是奇数，先取一个，成偶数
        res = a[r--];
        k--;
        if(res < 0) sign = -1;
    }
    while(k){  //负数每次只能取两个，所以都两个两个取
        LL x = (LL)a[l]*a[l+1],y = (LL)a[r-1]*a[r];
        if(x * sign > y * sign){
            res = x%mod *res%mod;
            l+=2;
        }else{
            res = y%mod*res%mod;
            r-=2;
        }
        k-=2;
    }
    printf("%lld\n",res);
    return 0;
}

技巧总结：贪心很简单。分类讨论不简单。代码实现较困难，要想想怎么节省代码空间。

后缀表达式 第十届C++ B T10

题意：给定 N 个加号、M 个减号以及 N+M+1 个整数。所能凑出的合法的后缀表达式中，结果最大的是哪一个？

思考：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;
const int mod=1000000009;
int n,m,len;
LL a[1000010];
LL ans;
int main(){
    cin>>n>>m;
    len=n+m+1;
    if(m==0){
        for(int i=1;i<=len;i++){
            scanf("%lld",&a[i]);
            ans+=a[i];
        }
    }else{
        LL mx=-100000000,mi=100000000;
        for(int i=1;i<=len;i++) {
            scanf("%lld", &a[i]);
            ans+=abs(a[i]);
            mx=max(mx,a[i]);
            mi=min(mi,a[i]);
        }
        ans-=abs(mx);
        ans-=abs(mi);
        ans+=(mx-mi);
    }

    cout<<ans;
    return 0;
}

技巧总结：熟悉后缀表达式，二叉树的后序遍历

灵能传输

题意： n名武士,每个人有一个灵能值 ai 表示其拥有的灵能的多少,可以进行任意次操作：$a_{i-1}+=a_i,a_{i+1}+=a_i,a_i-=2a_i$，问若干次操作后最小的$max^n_{i=1}|a_i|$是多少。

思考：先处理出差分数组，发现每一次操作相当于差分数组相邻两个数交换。我们可以通过直接计算max(s[i]-s[i-1]的值 获得最大值的最小值。

但问题在于 s[0],s[n]，按照题意他们是没办法交换的。那么就要使得差分排列成s形，在y轴重叠的地方各一个排一个。具体见题解：https://www.acwing.com/solution/content/97431/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 300010;

int n;
LL a[N], s[N];
bool st[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        s[0] = 0;
        for (int i = 1; i <= n; i ++ )
        {
            scanf("%lld", &a[i]);
            s[i] = s[i - 1] + a[i];
        }

        LL s0 = s[0], sn = s[n];
        if (s0 > sn) swap(s0, sn);
        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);
        int l = 0, r = n;
        for (int i = s0; i >= 0; i -= 2)
        {
            a[l ++ ] = s[i];
            st[i] = true;
        }
        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]));

        printf("%lld\n", res);
    }

    return 0;
}

技巧总结：先想明白操作等价于什么，再用贪心。