CF 1704D Magical Array

标签: cf

个长度为 的数组 ,初始内容相同,同时选定一个特殊数组

对于数组 有以下两个操作( 且操作不越界):

  1. 选定 ,然后 ;
  2. 选定 ,然后 ;

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

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

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

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;
}