【题解】CF1983C Have Your Cake and Eat It Too

这里是一份不怎么优雅的暴力模拟。

Solution

由于只有三个人参与了分配，通过排列原理可知可能的顺序有 $3!$ 种可能，通过定义函数对每种可能模拟即可，一旦合法输出相应方案。

AC Code

void solve()
{
    sum = 0, aver = 0;	// 记录总数和平均值
    cin >> n;
    for (int i = 1; i <= 3; i ++)
        for (int j = 1; j <= n; j ++) cin >> f[i][j];
        // 使用二维数组方便后面的函数分讨
    for (int i = 1; i <= n; i ++)
        sum += f[1][i];
    aver = (sum + 2) / 3;
    
    for (int a = 1; a <= 3; a ++)
        for (int b = 1; b <= 3; b ++)
            for (int c = 1; c <= 3; c ++)
                if (a != b && b != c && c != a)
                    if (work(a, b, c)) return;	// 全排列枚举
    puts("-1");	// 无解输出 -1
}

bool work(int a, int b, int c)
{
    ans[1].x = 1, ans[3].y = n;	// 答案的边界
    bool flag = false;	// 记录是否成立
    for (int i = 1, idx = 1, cur = 0; i <= n; i ++)	// idx 表示目前分到第几个人了
    {
        if (idx == 1) cur += f[a][i];
        else if (idx == 2) cur += f[b][i];
        else cur += f[c][i];
        
        if (cur >= aver)
        {
            if (idx == 1 || idx == 2) ans[idx ++].y = i, ans[idx].x = i + 1, cur = 0;
            else
            {
                flag = true;
                break;	// 合法就退出
            }
        }
    }
    if (flag)	// 输出方案
    {
        if (a == 2 && b == 3 && c == 1)
            printf("%d %d %d %d %d %d\n", ans[b].x, ans[b].y, ans[c].x, ans[c].y, ans[a].x, ans[a].y);
        else if (a == 3 && b == 1 && c == 2) 
            printf("%d %d %d %d %d %d\n", ans[c].x, ans[c].y, ans[a].x, ans[a].y, ans[b].x, ans[b].y);
        else printf("%d %d %d %d %d %d\n", ans[a].x, ans[a].y, ans[b].x, ans[b].y, ans[c].x, ans[c].y);
    }
    return flag;
}