0%

0-24 linked-list

從中間刪除?

如果我要刪除陣列最前最後的元素,可以用 deque 解決。

那,如果我今天要刪除陣列中間某個元素,或是在陣列中間插入某個元素,該怎麼做呢?

我們可以紀錄一個點的前、後方是誰,這樣的話,假設現在是1 -> 2 -> 3,如果我要刪除 2,我只要將 1 的後方指向 3、3 的前方指向 1,就能夠在 $O(1)$ 時間內完成刪除動作。

缺點

無法隨機存取,也就是說,無法快速知道當前的第 k 項是誰。只能知道頭、尾。

即使刪除一個元素只需要 $O(1)$,但是光是找到那個元素就要花 $O(N)$ 了啊。我要刪掉 2,但我不知道 2 在裡面的位置在哪裡,於是我只好從頭一個一個開始找,直到我找到 2,這也是非常慢的做法。

因此,linked-list 不太常被使用,雖然 STL 有 list 這個結構,但我還沒用過它。

唯一的用處

來看看這題:

ZJ 938

很明顯的,需要利用 linked-list 的概念來解決,只需要很簡單的刪除一個人後面的人就好。

那這題的瓶頸就在於,要如何維護一個人後面的人是誰。

一開始,每個人的後面都是自己的編號 + 1,當我刪除 1 後面的數 2 時,1 的後面就變成了原本 2 的後面 3,而其他人後面的數都不會被改變。

1
2
3
1 -> 2 -> 3 -> 4
1 -> X -> 3 -> 4 (2被殺)
1 ------> 3 -> 4 (1後面的人變成了原來2後面的人:3)

所以,我們開個陣列紀錄每個人現在後面是誰就好啦!完全不需要 STL 的 list 呢!事實上,list 根本沒有辦法做這題,因為找到一個人的位置需要 $O(N)$。

練習

ZJ b938

ZJ d718

★★★★ TIOJ 1225

★★★★ TIOJ 1930

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// ZJ b938
#include<bits/stdc++.h>
using namespace std;

int n, m;
int nxt[1000005], dead[1000005];

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++) nxt[i] = i+1;

for(int i=1,x;i<=m;i++){
cin >> x;
if(dead[x] || nxt[x] == n+1){
cout << "0u0 ...... ?\n";
continue;
}
cout << nxt[x] << '\n';
dead[nxt[x]] = 1;
nxt[x] = nxt[nxt[x]];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// ZJ d718
// 將沒有組別的人的編號設為 x + 10000,以避免與組混淆
// 題目沒說清楚,沒有組的人也有可能入列,例如範測 1 的 8
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n, team[1000005];
bool inq[10005];
queue<ll> q;
queue<ll> cur[10005];
string s;

void solve(){
fill(inq, inq+10001, 0);
fill(team, team+1000001, 0);
while(!q.empty()) q.pop();
for(int i=1;i<=10000;i++) while(!cur[i].empty()) cur[i].pop();
for(int i=1,x;i<=n;i++){
cin >> x;
for(int j=1,y;j<=x;j++){
cin >> y;
team[y] = i;
}
}
while(1){
cin >> s;
if(s[0] == 'E'){
int x;
cin >> x;
if(x > 1000000 || team[x] == 0){
q.push(10000+x);
}
else{
if(!inq[team[x]]) q.push(team[x]), inq[team[x]] = 1;
cur[team[x]].push(x);
}
}
else if(s[0] == 'D'){
if(q.front() >= 10000){
cout << q.front() - 10000 << '\n';
q.pop();
}
else{
cout << cur[q.front()].front() << '\n';
cur[q.front()].pop();
if(cur[q.front()].empty()){
inq[q.front()] = 0;
q.pop();
}
}
}
else break;
}
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t = 0;
while(cin >> n){
cout << "Line #" << ++t << '\n';
solve();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// TIOJ 1225
// 由小到大刪除元素
// 會使得結果變差的原因是,明明 b 能消掉 a,但 b 卻在 a 前就被消掉了。
// 為了不發生上述狀況,只要由小到大刪除元素就沒問題啦!
// 這題有 stack 的解,複雜度相同,但較好寫,可以試試想看看。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>

ll n, arr[1000005], fr[1000005], bk[1000005];

vector<pii> v;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i], fr[i] = i-1, bk[i] = i+1;
fr[n+1] = n;
bk[0] = 1;
arr[0] = arr[n+1] = 1e12;

for(int i=1;i<=n;i++) v.emplace_back(arr[i], i);
sort(v.begin(), v.end());

ll ans = 0;
for(int i=0;i<n-1;i++){
int idx = v[i].second;
if(arr[fr[idx]] > arr[bk[idx]]) ans += arr[bk[idx]];
else ans += arr[fr[idx]];

bk[fr[idx]] = bk[idx];
fr[bk[idx]] = fr[idx];
}

cout << ans << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// TIOJ 1930
// 麻煩的實作題,好好維護前面跟後面是誰
// 為什麼distribute操作不會 TLE 呢?
// 因為總共可能離開隊伍的人數 = 進入隊伍的人數 = N
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n, m, a1, fr[2000005], bk[2000005];

ll dump;
vector<int> ans;

void insert(int a, int b, int c){
if(c == 1){
bk[fr[b]] = a;
fr[a] = fr[b];
fr[b] = a;
bk[a] = b;
}
else{
fr[bk[b]] = a;
bk[a] = bk[b];
bk[b] = a;
fr[a] = b;
}
}

void rebuild(int a, int b, int c){
bk[fr[a]] = bk[b];
fr[bk[b]] = fr[a];

bk[fr[c]] = a;
fr[a] = fr[c];
fr[c] = b;
bk[b] = c;
}

void distribute(int a, ll b, int c){
if(c == 1){
int now = a;
for(int i=1;i<=b;i++){
if(now == 0){
dump += b-i+1;
break;
}
ans.emplace_back(now);
bk[fr[now]] = bk[now];
fr[bk[now]] = fr[now];
now = fr[now];
}
}
else{
int now = a;
for(int i=1;i<=b;i++){
if(now == n+1){
dump += b-i+1;
break;
}
ans.emplace_back(now);
bk[fr[now]] = bk[now];
fr[bk[now]] = fr[now];
now = bk[now];
}
}
}

void solve(){
dump = 0;
ans.clear();
fill(fr, fr+2000005, 0);
fill(bk, bk+2000005, 0);

cin >> n >> m >> a1;
bk[0] = a1, bk[a1] = n+1, fr[a1] = 0, fr[n+1] = a1;


for(int i=1,k,a,b,c;i<=m;i++){
cin >> k >> a >> b >> c;
if(k == 1) insert(a, b, c);
else if(k == 2) rebuild(a, b, c);
else distribute(a, b, c);
}
cout << dump << '\n';
for(auto i:ans) cout << i << '\n';
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t; cin >> t;
while(t--) solve();
}