国产精品免费嫩草研究院|无遮羞动漫在线观看AV|国产麻豆精品传媒AV国产在线|村在线观看|寂寞情人1正版|韩国床震韩国床震古|精品系列专区久久

  1. 首頁 > 生活 > >

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\)。
所有點的左側等效位置最左的位置，就是等效區(qū)間左端點；所有點的右側等效位置最右的位置就是等效區(qū)間的右端點 。
如果等效區(qū)間的左右端點來自于不同兩點的等效點，那么等效區(qū)間的中點一定在這兩點之間，否則原來的點必有一個能覆蓋另一個點，等效區(qū)間的左右端點就屬于同一個點的等效點 。
時間復雜度 \(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題解知識點：貪心 。
因為要字典序最小，那么一個數字他后面沒有更小的數字則可以保留，其他都應該刪除，所以從右往左找一個合法的保留序列，其他的數字加一，并且都是位置隨意的，于是可以插入到保留下來的序列，并使插入后的序列是從小到大字典序最小的排列 。因此直接把保留序列外的數字加一以后，對整個序列排序即可 。

經驗總結擴展閱讀