Div. 2 Codeforces Round #823 A-D _生活百科

比赛链接
A题解知识点：贪心。
对于一个轨道，要么一次性清理，要么一个一个清理。显然，如果行星个数大于直接清理的花费，那么选择直接清理，否则一个一个清理。即 \(\sum \min (c,cnt[i])\)，其中 \(cnt[i]\) 表示轨道 \(i\) 的行星个数。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int cnt[107];bool solve() {int n, c;cin >> n >> c;memset(cnt, 0, sizeof(cnt));for (int i = 1;i <= n;i++) {int x;cin >> x;cnt[x]++;}int ans = 0;for (int i = 1;i <= 100;i++) ans += min(c, cnt[i]);cout << ans << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}B题解方法一知识点：三分。
按位置从小到大排列，显然约会花费是一个关于 \(x_0\) 的单谷函数，因此可以三分位置。
由于位置最大有 \(10^8\) ，但点的个数只有 \(10^5\)，考虑先用 map 存储有序对 \((x,t)\)，其中 \(t\) 是位置 \(x\) 的人最大打扮时间，因为比这个时间少的一定不影响结果。遍历结束以后把 map 内容移到 vector 中用 pair 存储用以三分，check 函数则只要遍历一遍 vector 即可。
时间复杂度 \(O(n \log \max(eps))\)
空间复杂度 \(O(n)\)
方法二知识点：贪心。
把 \(t\) 等效进位置，如果 \(x_i\) 在 \(x_0\) 左侧，则等效位置是 \(xi - t\) ;如果 \(x_i\) 在 \(x_0\) 右侧，则等效位置是 \(x_i + t\)。
所有点的左侧等效位置最左的位置，就是等效区间左端点；所有点的右侧等效位置最右的位置就是等效区间的右端点。
如果等效区间的左右端点来自于不同两点的等效点，那么等效区间的中点一定在这两点之间，否则原来的点必有一个能覆盖另一个点，等效区间的左右端点就属于同一个点的等效点。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码方法一#include <bits/stdc++.h>#define ll long longusing namespace std;int x[100007];map<int, int> mp;vector<pair<int, int>> v;double check(double mid) {double mx = 0;for (auto [i, j] : v) {mx = max(mx, abs(i - mid) + j);}return mx;}bool solve() {mp.clear();v.clear();int n;cin >> n;for (int i = 1;i <= n;i++) {cin >> x[i];mp[x[i]] = 0;}for (int i = 1;i <= n;i++) {int T;cin >> T;mp[x[i]] = max(mp[x[i]], T);}for (auto [i, j] : mp) {v.push_back({ i,j });}double l = 0, r = v.back().first;while (abs(r - l) >= 1e-7) {double mid1 = l + (r - l) / 3;double mid2 = r - (r - l) / 3;if (check(mid1) <= check(mid2)) r = mid2;else l = mid1;}cout << fixed << setprecision(10) << l << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}方法二#include <bits/stdc++.h>#define ll long longusing namespace std;int x[100007], T[100007];bool solve() {int n;cin >> n;int l = 1e9, r = 0;for (int i = 1;i <= n;i++) cin >> x[i];for (int i = 1;i <= n;i++) cin >> T[i];for (int i = 1;i <= n;i++) {l = min(x[i] - T[i], l);///最左侧等效点r = max(x[i] + T[i], r);///最右侧等效点}cout << fixed << setprecision(8) << (l + r) / 2.0 << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}C题解知识点：贪心。
因为要字典序最?。?那么一个数字他后面没有更小的数字则可以保留，其他都应该删除，所以从右往左找一个合法的保留序列，其他的数字加一，并且都是位置随意的，于是可以插入到保留下来的序列，并使插入后的序列是从小到大字典序最小的排列。因此直接把保留序列外的数字加一以后，对整个序列排序即可。
也可以直接桶排序。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {string s;cin >> s;int mi = 10;for (int i = s.size() - 1;i >= 0;i--) {if (s[i] - '0' <= mi) mi = s[i] - '0';else s[i] = min(s[i] + 1, '9' + 0);}sort(s.begin(), s.end());cout << s << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}D题解知识点：构造。
注意到操作不会改变无序对 \((a_i, b_{ n - i + 1 })\) 数量以及种类。

Div. 2 Codeforces Round #823 A-D

推荐阅读

2023年大年初四十二生肖运势运气最佳生肖是什么？

女人喝黄酒的最好时间女人什么时候喝黄酒好

蒸燕窝多少时间蒸燕窝需要多长时间

在美国并不是所有的州都庆祝哥伦布纪念日哥伦布纪念日如何庆祝

武汉非机动车牌照补办需要哪些前提武汉非机动车牌照补办需要哪些前提材料

如何识别兰花好坏如何识别兰花好坏？

治疗皮肤病老中医小妙方帮您远离皮肤病

实用新型多久可授权

留学必备的GPA到底怎么换算 gpa怎么算

梦见脸上长皱纹

360全民医保怎么退

如何创建网页快捷方式到桌面，如何将网页以快捷方式保存在桌面？

罗姓男孩名字大全属虎虎年罗姓男宝宝名字

雅鲁藏布江大峡谷产生的原因雅鲁藏布江大峡谷产生的原因

刮痧是排毒的表现吗刮痧排毒的原理是什么

怎样修改路由器wifi密码 192.168.11路由器设置教程

做深蹲后大腿粗怎么办女性深蹲很难粗腿

关于消防安全管理人简述消防安全管理人

关于海因茨·弗洛赫简述海因茨·弗洛赫

iphone屏蔽短信广告 iphone屏蔽短信