# 11051: 【原1051】静态查找表

### 题目描述

author: yepyao 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1051

## Hint

Hint：你的程序只能判断两个整数是相等或是不相等，也就是说，认为静态查找表中的元素是无序的！

## Sample Input

3
1
3
4
3
2
1
4


## Sample Output

7


## FineArtz's solution

/* 静态查找表 */
#include <iostream>
using namespace std;

class Node{
public:
Node *pred = nullptr, *succ = nullptr;
int data = 0;
};

int main(){
int n, m, cnt = 0;
cin >> n;
for (int i = 1; i <= n; ++i){
Node *t = new Node;
cin >> t->data;
p->succ = t;
t->pred = p;
p = t;
}
cin >> m;
while (m--){
int x;
cin >> x;
while (p){
++cnt;
if (p->data == x)
break;
p = p->succ;
}
if (p){
p->pred->succ = p->succ;
if (p->succ)
p->succ->pred = p->pred;
if (p->succ)
p->succ->pred = p;
}
}
while (p){
q = p->succ;
delete p;
p = q;
}
cout << cnt << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"
using namespace std;

class myList {
public:
class node {
public:
int data;
node* next = nullptr;
};

node* rear;
myList() {
}

~myList() {
for (auto p = head; p!= nullptr;) {
auto temp = p;
p = p->next;
delete temp;
}
}

int find(int num) {
int ans = 0;
for (; p->next != nullptr; p = p->next,ans++) {
if (p->next->data == num) {
ans++;
break;
}
}
//移动
}
return ans;
}

void insert(int num) {
bool flag = true;
/*for (; p->next != nullptr; p = p->next)
if (p->next->data == num) {
flag = false;
break;
}*/

if (flag) {
rear->next = new node;
rear = rear->next;
rear->data = num;
}
}
};

int main() {
ios::sync_with_stdio(false);

int n, m;
cin >> n;

myList newList;

for (; n > 0; n--) {
int temp;
cin >> temp;
newList.insert(temp);
}

cin >> m;

long long ans = 0;
for (; m > 0; m--) {
int temp;
cin >> temp;
ans += newList.find(temp);
}

cout << ans;

return 0;
}


## Neight99's solution

#include <iostream>

using namespace std;

int compare = 0;

private:
struct Node {
int data;
Node *next;

Node() : data(0), next(NULL) {}
Node(int d, Node *n = NULL) : data(d), next(n) {}
~Node() {}
};
int Length;

Node *move(int) const;

public:
void push_back(const int &);
void push_first(const int &);
void clear();
void remove(const int &);
int find(const int &);
void moveToFirst(const int &);
int visit(const int &);
};

while (i-- >= 0) {
p = p->next;
}

return p;
}

Length = 0;
}

clear();
}

while (p != NULL) {
q = p->next;
delete p;
p = q;
}
Length = 0;
}

Node *p = move(Length - 1);
p->next = new Node(x, p->next);
++Length;
}

p->next = new Node(x, p->next);
++Length;
}

if (i == -1) {
return;
} else {
Node *p, *q;
p = move(i - 1);
q = p->next;
p->next = q->next;
delete q;
--Length;
}
}

int n = 0;
while (p != NULL) {
compare++;
if (p->data == x) {
return n;
} else {
p = p->next;
n++;
}
}

return -1;
}

int sLinkList::visit(const int &x) { return move(x)->data; }

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n, m, tmp, pos;

cin >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
lists.push_back(tmp);
}

cin >> m;
for (int i = 0; i < m; i++) {
cin >> tmp;
pos = lists.find(tmp);
if (pos != -1) {
lists.remove(pos);
lists.push_first(tmp);
}
}

cout << compare;

return 0;
}


## satgo1546's solution

#include <cstdio>
using namespace std;

int n;
// 不使用此数组中的第0个元素，以零next作为表尾。
struct {
int x, next;
} a[100007];
int s;

void search(int x) {
int prev = 0;
while (i) {
s++;
if (a[i].x == x) {
if (prev) {
a[prev].next = a[i].next;
}
return;
}
prev = i;
i = a[i].next;
}
}

int main(int argc, char **argv) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i].x);
a[i].next = i + 1;
}
a[n].next = 0;
scanf("%d", &argc);
while (argc--) {
int x;
scanf("%d", &x);
search(x);
}
printf("%d\n", s);
return 0;
}


## WashSwang's solution

#include <iostream>
using namespace std;
int ans,n,x,m,nex[20000],v[20000],last;
int main() {
cin>>n;
for (int i=1;i<=n;++i)
{
cin>>v[i];
nex[i-1]=i;
}
cin>>m;
for (int i=0;i<m;++i)
{
cin>>x;
last=0;
for (int j=nex[0];j;j=nex[j]){
ans++;
if (v[j]==x){
nex[last]=nex[j];
nex[j]=nex[0];
nex[0]=j;
break;
}
last=j;
}
}
cout<<ans;
return 0;
}


## yyong119's solution

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 10001;

int main() {

int n, m;
long times = 0;
int a[MAXN];
memset(a, 0, sizeof(a));
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
scanf("%d", &m);
while (m) {
scanf("%d", &a[0]);
for (int i = 1; i <= n; ++i) {
++times;
if (a[i] == a[0]) {
for (int j = i; j >= 1; --j) a[j] = a[j - 1];
break;
}
}
--m;
}
printf("%d\n", times);
}