Codeforces Round 638 (Div. 2)___F. Phoenix and Memory —— 贪心 +线段树

本文主要是介绍Codeforces Round 638 (Div. 2)___F. Phoenix and Memory —— 贪心 +线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个人标号为 $1$ ~ $n$，顺序被打乱后
    第 $i$ 个人的标号在 $[L_i,R_i]$ 之间
    保证答案存在，若答案唯一，则输出唯一答案
    若不唯一，则输出任意两种答案

解题思路：

    考虑先弄出一组答案：
    按照 $L_i$ 排序，枚举加入 $L_i$ 后，当前肯定选择 $R_i$ 最小的那个人
    这样肯定是最贪心的，用一个 $set$ 维护即可

---

    记标号为 $i$ 的人打乱后位置在 $po{s}_i$
    考虑什么情况下两个人的标号可以交换：
    $L[po{s}_i]\le i\le R[po{s}_i]$
    $L[po{s}_j]\le j\le R[po{s}_j]$

    假设 $i＜j$，要满足 $i$ 和 $j$ 可以交换
    必须满足：$L[po{s}_j]\le i＜j\le R[po{s}_i]$
    也就是枚举 $i$，只需要找到一个 $j$ 满足上式即可

    由于 $R[po{s}_i]$ 已知，也就是在标号为 $[i+1,R[po{s}_i]]$ 里找到一个 $j$
    其 $L[po{s}_j]$ 最小，若 $L[po{s}_j]\le i$，则满足交换，这部分可以用线段树实现
    注意 $i＞j$ 的情况是一样的，但是枚举 $i＜j$ 就包括所有情况了
    $i$ 和 $po{s}_i$ 绕来绕去要分清楚

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 2e5 + 5;
int n, pos[maxn], L[maxn], R[maxn], ans[maxn];
int t[maxn<<2], id[maxn<<2];
vector <pii> v[maxn]; 
set <pii> s;void build(int l, int r, int rt){if(l == r){t[rt] = L[pos[l]];id[rt] = l;return;}int mid = l + r >> 1;build(l, mid, rt<<1);build(mid+1, r, rt<<1|1);if(t[rt<<1] < t[rt<<1|1]) t[rt] = t[rt<<1], id[rt] = id[rt<<1];else t[rt] = t[rt<<1|1], id[rt] = id[rt<<1|1];
}pii query(int ql, int qr, int l, int r, int rt){if(r<ql || l>qr) return {1e9, 0};if(l>=ql && r<=qr) return {t[rt], id[rt]};int mid = l + r >> 1; pii ret = {1e9, 0};ret = min(ret, query(ql, qr, l, mid, rt<<1));ret = min(ret, query(ql, qr, mid+1, r, rt<<1|1));return ret;
}signed main() {scanf("%d", &n);for(int i=1; i<=n; i++){scanf("%d%d", L+i, R+i);v[L[i]].push_back({R[i], i});}for(int i=1; i<=n; i++){s.insert(v[i].begin(), v[i].end());pos[i] = (*s.begin()).second;ans[pos[i]] = i;s.erase(s.begin());}build(1, n, 1); for(int i=1; i<=n; i++){if(i + 1 > R[pos[i]]) continue;pii q = query(i+1, R[pos[i]], 1, n, 1);int q1 = q.first, q2 = q.second;if(q1 == 1e9 || q1 > i) continue;puts("NO");for(int i=1; i<=n; i++) printf("%d ", ans[i]);puts(""); swap(ans[pos[i]], ans[pos[q2]]);for(int i=1; i<=n; i++) printf("%d ", ans[i]);puts(""); return 0;}puts("YES");for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

这篇关于Codeforces Round 638 (Div. 2)___F. Phoenix and Memory —— 贪心 +线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---