#P2961. 第2题-记忆碎片
-
1000ms
Tried: 16
Accepted: 5
Difficulty: 7
所属公司 :
阿里
时间 :2025年5月17日-阿里淘天(开发岗)
-
算法标签>思维
第2题-记忆碎片
题面描述 你有 n 块记忆碎片,排成一行,第 i 块碎片的时间标签为 ti,(t1,t2,…,tn) 是 1 到 n 的一个排列。 你希望通过交换把它们重排为 [1,2,…,n]。每次操作:
- 任选两块标签差值 ≤k 的碎片交换;
- 若两标签差值恰为 1,消耗 1 点精力;
- 若两标签差值在 [2,k] 之间,免费(消耗 0 点精力)。
求:完成排序所需的最少精力。
思路
-
如果 k≥3,任何两标签间都能借助“差值≥2”的免费交换连通,全程不耗能量,答案直接为 0。
-
否则分两种情况:
-
k=1:只能做差值为 1 的交换,每次都要耗能量,等价于对整个排列做相邻交换统计逆序对总数
1≤i<j≤n∑[ti>tj] -
k=2:差值为 2 的交换免费,可在“同奇偶”标签之间任意重排;只有“奇↔偶”标签的逆序需要消耗能量。最少精力即所有逆序对中“奇偶性不同”的数目

-
-
统计手段:
- k=1 时,用归并排序法 O(nlogn) 统计全逆序对。
- k=2 时,维护两棵树状数组(BIT):一棵存右侧剩余的奇数标签计数,一棵存偶数计数;扫描时对每个元素查询并累加与其不同奇偶的、比它小的右侧标签数量。
C++
#include <bits/stdc++.h>
using namespace std;
// 归并法统计全部逆序对(k=1)
long long count_all_inv(vector<int>& a) {
int n = a.size();
vector<int> tmp(n);
function<long long(int,int)> dfs = [&](int l, int r) {
if (r-l <= 1) return 0LL;
int m = (l + r) >> 1;
long long cnt = dfs(l, m) + dfs(m, r);
int i = l, j = m, p = l;
while (i < m || j < r) {
if (j==r || (i<m && a[i]<=a[j])) tmp[p++] = a[i++];
else {
cnt += (m - i);
tmp[p++] = a[j++];
}
}
for (int k = l; k < r; k++) a[k] = tmp[k];
return cnt;
};
return dfs(0, n);
}
// 树状数组(Fenwick Tree)
struct BIT {
int n;
vector<int> t;
BIT(int _n): n(_n), t(n+1,0) {}
void update(int i, int v=1) {
for (; i<=n; i+=i&-i) t[i]+=v;
}
int query(int i) {
int s=0;
for (; i>0; i-=i&-i) s+=t[i];
return s;
}
int query(int l, int r) {
return query(r) - query(l-1);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> t(n);
for (int i = 0; i < n; i++) cin >> t[i];
if (k >= 3) {
// 全程免费
cout << 0 << "\n";
return 0;
}
if (k == 1) {
// 只允许相邻交换,耗能 = 全逆序对数
cout << count_all_inv(t) << "\n";
return 0;
}
// k == 2:免费交换同奇偶,只计算奇偶不同的逆序对
BIT bit_even(n), bit_odd(n);
// 初始化:把所有标签放入对应 BIT
for (int x : t) {
if (x & 1) bit_odd.update(x);
else bit_even.update(x);
}
long long ans = 0;
// 从左向右,把当前标签从“右侧集合”中移出,并查询与之不同奇偶且小于它的剩余标签数
for (int x : t) {
if (x & 1) {
bit_odd.update(x, -1);
ans += bit_even.query(x-1);
} else {
bit_even.update(x, -1);
ans += bit_odd.query(x-1);
}
}
cout << ans << "\n";
return 0;
}
Python
import sys
sys.setrecursionlimit(10**7)
# 归并法统计全部逆序对(k=1)
def merge_all(a, tmp, l, r):
if r-l <= 1: return 0
m = (l+r)//2
cnt = merge_all(a, tmp, l, m) + merge_all(a, tmp, m, r)
i, j, p = l, m, l
while i < m or j < r:
if j==r or (i<m and a[i]<=a[j]):
tmp[p] = a[i]; i += 1
else:
cnt += (m - i)
tmp[p] = a[j]; j += 1
p += 1
a[l:r] = tmp[l:r]
return cnt
# 树状数组
class BIT:
def __init__(self,n):
self.n = n
self.t = [0]*(n+1)
def update(self,i,v=1):
while i<=self.n:
self.t[i] += v
i += i&-i
def query(self,i):
s = 0
while i>0:
s += self.t[i]
i -= i&-i
return s
def range_query(self,l,r):
return self.query(r) - self.query(l-1)
def main():
data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
t = data[2:]
if k >= 3:
print(0)
return
if k == 1:
tmp = [0]*n
print(merge_all(t, tmp, 0, n))
else:
# k == 2
bit_even = BIT(n)
bit_odd = BIT(n)
for x in t:
if x & 1: bit_odd.update(x)
else: bit_even.update(x)
ans = 0
for x in t:
if x & 1:
bit_odd.update(x, -1)
ans += bit_even.query(x-1)
else:
bit_even.update(x, -1)
ans += bit_odd.query(x-1)
print(ans)
if __name__ == "__main__":
main()
Java
import java.io.*;
import java.util.*;
public class Main {
// 归并统计全部逆序对(k=1)
static long mergeAll(int[] a, int l, int r, int[] tmp) {
if (r - l <= 1) return 0;
int m = (l + r) >> 1;
long cnt = mergeAll(a, l, m, tmp) + mergeAll(a, m, r, tmp);
int i = l, j = m, p = l;
while (i < m || j < r) {
if (j==r || (i<m && a[i] <= a[j])) tmp[p++] = a[i++];
else {
cnt += (m - i);
tmp[p++] = a[j++];
}
}
System.arraycopy(tmp, l, a, l, r-l);
return cnt;
}
// 树状数组
static class BIT {
int n;
int[] t;
BIT(int n) { this.n = n; t = new int[n+1]; }
void update(int i, int v) {
while (i <= n) { t[i] += v; i += i & -i; }
}
int query(int i) {
int s = 0;
while (i > 0) { s += t[i]; i -= i & -i; }
return s;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
int[] t = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) t[i] = Integer.parseInt(st.nextToken());
if (k >= 3) {
System.out.println(0);
return;
}
if (k == 1) {
System.out.println(mergeAll(t, 0, n, new int[n]));
} else {
// k == 2
BIT bitEven = new BIT(n), bitOdd = new BIT(n);
for (int x : t) {
if ((x & 1) == 1) bitOdd.update(x, 1);
else bitEven.update(x, 1);
}
long ans = 0;
for (int x : t) {
if ((x & 1) == 1) {
bitOdd.update(x, -1);
ans += bitEven.query(x-1);
} else {
bitEven.update(x, -1);
ans += bitOdd.query(x-1);
}
}
System.out.println(ans);
}
}
}
题目内容
你得到了n块[记忆碎片],它们排成一排,第i块碎片所对应记忆发生的时间为ti。t1,t2,...,tn是1到n的一个排列。
你希望重新排列这n块碎片,使它们单调递增(即重排为1,2,...,n),排列的规则为:
-
你有一个能力值k,每次你可以选择两块发生时间相差不超过k的碎片,交换它们的顺序;
-
由于发生时间过于靠近的两块碎片很难回想,对于两块发生时间相差恰好为1的碎片,交换它们需要消耗你1点精力;
-
对于发生时间相差大于1的碎片,变换它们则不需要耗费精力。
你想知道你最少需要消耗多少精力才能恢复你的[记忆]。
输入描述
第一行输入两个整数n,k(4≦n≦2×105;1≦k≦n−1)代表[记忆碎片]的个数、你的能力值。
第二行输入n个不同的整数t1,t2,...,tn(1≦ti≦n),其中,ti代表第i块[记忆碎片]所对应记忆的发生时间。
输出描述
输出一个整数,表示你最少需要消耗的精力。
样例1
输入
4 1
2 1 3 4
输出
1
说明
在这个样例中,交换t1和t2即可,我们可以证明,最少需要消耗1点精力
样例2
输入
4 3
2 1 3 4
输出
0
说明
最优交换策略为:
-
交换t2 和t4,得到{2,4,3,1};
-
交换t1和t2,得到{4,2,3,1};
-
交换t1和t4,得到{1,2,3,4}。
至此,t已经有序,最少需要消耗0点精力。