专栏文章

题解：P9310 [EGOI2021] Luna likes Love / 卢娜爱磕 cp

PPig_Eat_Earth
P9310题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqjg8o9
此快照首次捕获于
2025/12/04 05:48
3 个月前
此快照最后确认于
2025/12/04 05:48
3 个月前
查看原文

P9310题解

题目大意

给定一个长度为 2n2n 的正整数序列，保证所有 1≤i≤n1\le i\le n 恰好出现两次，有以下两种操作，求清空序列的最小操作数：
  • 交换相邻两个元素
  • 删除两个相邻且相等的元素（让情侣去约会）

解法 A

思路

明显地，删除操作的次数恒为 nn，因此只需要找出一个操作序列使得交换次数最少。
观察发现通过交换让一对情侣排在一起的操作次数等于他们之间间隔的人数。
考虑贪心。按照间隔人数升序依次操作，每次答案加上他们之间还剩余的人数。
维护剩余人数需要进行单点修改、区间查询操作（即对于一次约会操作，需要查询区间内剩余人数，然后删除一对情侣）。于是考虑采用树状数组。

时间复杂度

树状数组初始化：O(n)O(n)。
贪心排序：O(n)O(n)。
“约会”操作：每对情侣约会一次，树状数组 O(log⁡n)O(\log n)，共 O(nlog⁡n)O(n\log n)。
总时间复杂度：O(nlog⁡n)O(n\log n)。
注：树状数组初始化可以在输入时完成，具体见代码

对于贪心正确性的证明

假设有两对情侣，位置分别为 a1/a2a_1/a_2 以及 b1/b2b_1/b_2，满足 a1<a2a_1<a_2 且 b1<b2b_1<b_2 且 a2−a1<b2−b1a_2-a_1<b_2-b_1。由上述贪心策略可以得知，情侣 aa 应在情侣 bb 前约会。下证 bb 在 aa 前约会，答案不会变好（有可能变差）。
分类讨论 aa 与 bb 的位置关系。
注：证明过程中所求两次操作答案均不考虑其他情侣的影响，因为其他情侣对顺序交换与否的答案的影响相等
  1. a1<a2<b1<b2a_1<a_2<b_1<b_2 或 b1<b2<a1<a2b_1<b_2<a_1<a_2
    无影响。
  2. a1<b1<a2<b2a_1<b_1<a_2<b_2 或 b1<a1<b2<a2b_1<a_1<b_2<a_2 顺序不交换，则 aa 的交换次数为 a2−a1a_2-a_1，bb 的交换次数为 b2−b1−1b_2-b_1-1。
    顺序交换，则 bb 的交换次数为 b2−b1b_2-b_1，aa 的交换次数为 a2−a1−1a_2-a_1-1。
    可得，无论顺序交换与否，两次操作总交换次数均为 (a2−a1)+(b2−b1)−1(a_2-a_1)+(b_2-b_1)-1。
  3. b1<a1<a2<b2b_1<a_1<a_2<b_2
    顺序不交换，则 aa 的交换次数为 a2−a1a_2-a_1，bb 的交换次数为 b2−b1−2b_2-b_1-2。
    顺序交换，则 bb 的交换次数为 b2−b1b_2-b_1，但 ∵b1,b2∉[a1,a2]\because b_1,b_2\notin [a_1,a_2]，∴a\therefore a 的交换次数仍为 a2−a1a_2-a_1。
    在此情况中，顺序不交换比交换更优。
综上，顺序不交换比交换更优或一样。一般地，操作顺序应按情侣间隔人数多少升序排列。
证毕。

AC Code

CPP
#include <bits/stdc++.h>
#define int long long //记得开long long 
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 5e5, A = N << 1;
int n, a[A + 5], tr[A + 5], ans;
struct CP{
	int n, f, s;
} cp[N + 5];

bool cmp(CP a, CP b){
	return a.s - a.f < b.s - b.f;
}

void mns(int x){ for(; x <= (n << 1); x += lowbit(x)) -- tr[x]; }

int get(int x){
	int res = 0;
	for(; x; x -= lowbit(x)) res += tr[x];
	return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	ans = n;
	for(register int i = 1; i <= (n << 1); ++ i){
		cin >> a[i];
		(cp[a[i]].f ? cp[a[i]].s : cp[a[i]].f) = i;
		tr[i] = lowbit(i); // 树状数组全部置1 
	}
	for(register int i = 1; i <= n; ++ i) cp[i].n = i;
	sort(cp + 1, cp + n + 1, cmp);
	for(register int i = 1; i <= n; ++ i){
		ans += get(cp[i].s - 1) - get(cp[i].f);
		mns(cp[i].f);
		mns(cp[i].s);
	}
	cout << ans;
	return 0;
}

解法 B

思路

准备好一个“栈”。
遍历 aa 数组，如果该元素不在栈中（第一次出现），则入栈；否则（第二次出现），将答案加上栈内该元素到栈顶的距离，并弹出栈内该元素。
考虑到一般的栈无法实现任意查询与弹出，使用树状数组模拟“栈”。

时间复杂度

对于 aa 数组中的每一个元素，都要使用树状数组进行查改，故时间复杂度为 O(nlog⁡n)O(n\log n)。

AC Code

考试代码，没开 long long 拿了 8484。
CPP
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
using namespace std;
int n, a[1000006], tim[500005], tot, tr[500005];

void add(int x){
	tim[x] = ++ tot;
	for(register int i = tot; i <= n; i += lowbit(i)) ++ tr[i];
}

void del(int x){
	for(register int i = tim[x]; i <= n; i += lowbit(i)) -- tr[i];
	tim[x] = 0;
}

int get(int x){
	int res = 0;
	for(; x; x -= lowbit(x)) res += tr[x];
	return res;
}

void solve(){ //一开始想暴力骗分，题解中删掉了
	long long ans = n; // 只需要这里开long long
	for(register int i = 1; i <= (n << 1); ++ i){
		if(tim[a[i]]){
			ans += get(tot) - get(tim[a[i]]);
			del(a[i]);
		}
		else add(a[i]);
	}
	cout << ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(register int i = 1; i <= (n << 1); ++ i) cin >> a[i];
	solve();
	return 0;
}

注意事项

long long

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...