codeforces 500C New Year Book Reading

题目链接：codeforces 500C

这个题，不是难在写代码，而是难在了如何去证明这个结论（其实猜想也是只要胆子大，就是可以过的）

关键是从样例中找到这个题的解法！

书的初始排列顺序是定好的！

就是按照m本书的给定数据，从前到后，建立一个链表，然后去暴力操作就好！

证明是所谓的理论证明吧，就是读的书是需要把该书上面的书全部拿走的。那么，越早阅读的书，放在越上面越好咯

那么，涉及到最重要的问题

数据结构是个链表：在暴力找到了需要读的书之后，需要把这个节点删除，然后插入到起点和起点的后一个点之中

然后就是个看基本功的题了

#include<bits/stdc++.h>
using namespace std;

const int maxn=550;
const int maxm=1050;
struct node{
	int L,R;
}a[maxn];
int c[maxn],x[maxm];
int mp[maxm],n,m,ans,tot;
bool vis[maxm];
int Head,Tail;

void debug(){
	//GetRight
	int pos=Head;
	while(pos!=Tail){
		pos=a[pos].R;
		//cout<<c[pos]<<endl;
		cout<<pos<<" ";
	}
	cout<<endl;
	pos=Tail;
	while(pos!=Head){
		pos=a[pos].L;
		//cout<<pos<<endl;
		cout<<pos<<" ";
	}
	cout<<endl;
	cout<<endl;
}

int main(){
	//freopen("input1.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		c[0]=0;
		c[n+1]=0;
		for(int i=1;i<=n;i++) scanf("%d",&c[i]);
		memset(vis,false,sizeof(vis));
		ans=tot=0;
		for(int i=1;i<=m;i++){
			scanf("%d",&x[i]);
			if (!vis[x[i]]){
				vis[x[i]]=true;
				mp[++tot]=x[i];
			}
		}
		memset(a,-1,sizeof(a));
		Head=0;
		Tail=n+1;
		a[Head].R=mp[1];
		a[Tail].L=mp[tot];
		for(int i=1;i<=tot;i++)
			if (i==1){
				a[mp[i]].L=Head;
				a[mp[i]].R=mp[i+1];
			}
			else if (i==n){
				a[mp[i]].R=Tail;
				a[mp[i]].L=mp[i-1];
			}
			else{
				a[mp[i]].L=mp[i-1];
				a[mp[i]].R=mp[i+1];
			}
		for(int i=1;i<=m;i++){
			int pos=Head,temp=0;
			while(pos!=x[i]){
				temp+=c[pos];
				pos=a[pos].R;
				//cout<<pos<<" ";
			}
			//cout<<temp<<endl;
			//debug();
			ans+=temp;
			a[a[pos].L].R=a[pos].R;
			a[a[pos].R].L=a[pos].L;
			a[pos].R=a[Head].R;
			a[pos].L=Head;
			a[a[Head].R].L=pos;
			a[Head].R=pos;
		}
		printf("%d\n",ans);
	}
	return 0;
}