贪心+构造，CF 761D - Dasha and Very Difficult Problem

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

761D - Dasha and Very Difficult Problem

---

二、解题报告

1、思路分析

如果我们知道 c，那么根据 c[i] = b[i] - a[i]，我们相当于得到了 b[]

如何得到c？

我们知道了 c 各个下标元素排名

以及每个元素的范围：[l - a[i], r - a[i]]

那么我们贪心的从低往上构造

显然越小越好，这样上面的元素容错率越高

即 最小的构造为 l - p[i]，次小的构造为 max(l - p[i] + 1, l - a[j])……

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;void solve() {int n, l, r;std::cin >> n >> l >> r;std::vector<int> a(n);for (int i = 0; i < n; ++ i) std::cin >> a[i];std::vector<int> p(n);for (int i = 0; i < n; ++ i) std::cin >> p[i];std::vector<int> id(n);std::iota(id.begin(), id.end(), 0);std::ranges::sort(id, [&](int i, int j) -> bool {return p[i] < p[j];});std::vector<int> ans(n);ans[id[0]] = l - a[id[0]];for (int i = 1; i < n; ++ i) {if (p[id[i]] == p[id[i - 1]])ans[id[i]] = ans[id[i - 1]];else {ans[id[i]] = std::max(ans[id[i - 1]] + 1, l - a[id[i]]);}}for (int i = 0; i < n; ++ i) {ans[i] += a[i];if (ans[i] > r) {std::cout << -1 << '\n';return;}}for (int i = 0; i < n; ++ i) {std::cout << ans[i] << " \n"[i + 1 == n];}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}