题目链接: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好写一点:)
- 数据结构 Educational Codeforces 结构 数学数据结构educational codeforces结构 educational codeforces数学 动态 educational codeforces思维 数学 数据结构codeforces结构 数学 educational codeforces round rated 数据结构 性质 结构 数学 educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round