從中間刪除？
如果我要刪除陣列最前最後的元素，可以用 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
|
#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
|
#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
|
#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
|
#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();
}
|