CF 1704D Magical Array

標籤： cf

有 $n$ 个长度为 $m$ 的数组 $c_{i,j}$，初始内容相同，同时选定一个特殊数组 $c_k$。

对于数组 $c_t$ 有以下两个操作（$i < j$ 且操作不越界）：

1. 选定 $i$，$j$，然后 $c_{t,i} \gets c_{t,i} - 1$，$c_{t,j} \gets c_{t,j} - 1$， $c_{t,i-1} \gets c_{t,i-1} + 1$，$c_{t,j+1} \gets c_{t,j+1} + 1$;
2. 选定 $i$，$j$，然后 $c_{t,i} \gets c_{t,i} - 1$，$c_{t,j} \gets c_{t,j} - 1$， $c_{t,i-1} \gets c_{t,i-1} + 1$，$c_{t,j+2} \gets c_{t,j+\mathbf{2}} + 1$;

操作 1 只能在非特殊数组上使用，操作 2 只能在特殊数组上使用，每个数组至少有一次操作。

给定操作后的 $n$ 个数组，求特殊数组的编号及其被操作次数。

考虑将数组 $c_i$ 看成差分数组，令其前缀和为 $s_i$， 操作 1，2 就变成了区间操作，发现操作 2 的减法操作的区间明显要大一些，由此发现每次操作 2，$\sum s$ 便减 $1$。

void solve()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<long long>> c(n, std::vector<long long>(m));
    std::vector<long long> ss(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            std::cin >> c[i][j];
        }
        std::partial_sum(c[i].begin(), c[i].end(), c[i].begin());
        ss[i] = std::accumulate(s[i].begin(), s[i].end(), 0ll);
    }
    int key = std::min_element(ss.begin(), ss.end()) - ss.begin();
    std::cout << key + 1 << " " << ss[(key + 1) % n] - ss[key] << std::endl;
}