526互联

Educational Codeforces Round 150 (Rated for Div. 2)E. Fill the Matrix（数据结构，数学）

发布时间 2023-08-30 10:34:40作者: XiCen

题目链接：https://codeforces.com/contest/1841/problem/E

 

题意：

 

有一个nxn的正方形网格；

 

现在对每一列进行约束，对第 i 列 从上往下，将 a[ i ] 个格子涂成黑色；

 

给正整数m，你要在网格内填上 1 ~ m 个数，有以下限制：

 

1： 数字只能填在白色格子里；

 

2：每个白色格子只能填一个数字；

 

现在，我们要最大化出现以下的情况的格子：

 

该格子内的数字是 j ，在他相邻的右边的 格子的数字是 j + 1；

 

问这样子的格子有最多有多少个；

 

分析：

 

考虑最终的图形，每行都被分成了诺干段；

 

可以看出，如果一段的长度是 x ，我们将他们依次填满，会出现 x - 1个满足条件的格子；

 

为了最大化最终的结果，所以我们依次选择长度最长的段进行填充，是最优的方案；

 

那么接下来我们就要思考 长度为 1 ~ n的线段分别有多少；

 

我们考虑从下往上一行一行来考虑：

 

对于约束 a【i】 来说，我们把约束来排序，a【i】大的在我们从下往上枚举的过程中最先遇到；

 

遇到a【i】的约束，相当于一条线段中出现一个点，把这个长线段分为俩个小的线段；

 

我们记录这个线段俩端的点出现的时间（最下面那行开始的时间的n，然后依次减小），取时间最小的那个点，与现在遇到约束的时间点来比较，那么他们的插值就是线段长度出现的次数；

 

我们用set来记录上面的线段；

 

时间复杂度：O（nlogn）

 

代码：

#include<bits/stdc++.h>

#define int long long

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int T;
    std::cin >> T;
    while (T--) {
        int n;
        std::cin >> n;
        std::vector<std::vector<int>> pos(n + 1);

        for (int i = 1; i <= n; ++i) {
            int x;
            std::cin >> x;
            pos[x].push_back(i);
        }

        std::set<int> seg;
        std::vector<int> tim(n + 2, 0), cnt(n + 1, 0);
        tim[0] = tim[n + 1] = n;
        seg.insert(0);
        seg.insert(n + 1);

        for (int i = n; i >= 0; i--) {
            for (auto x: pos[i]) {
                auto it = seg.lower_bound(x);
                int pre = *prev(it);
                int suf = *it;
                int from = std::min(tim[pre], tim[suf]);
                cnt[suf - pre - 1] += from - i;
                seg.insert(x);
                tim[x] = i;
            }
        }

        int m;
        std::cin >> m;
        int ans = 0;
        for (int i = n; i >= 1 && m; --i) {
            int k = std::min(cnt[i], m / i);
            ans += k * (i - 1);
            m -= k * i;
            cnt[i] -= k;
            cnt[i - 1] += cnt[i];
        }

        std::cout << ans << "\n";
    }

    return 0;
}

当然，这题还可以用线段树等高级科技搞过，本人觉得用set好写一点：）