Codeforces 1279C Stack of Presents

题目链接:

Codeforces 1279C Stack of Presents

思路:

挨个取礼物,维护历史取到的最低层;
如果当前礼物的层次高于最底层,那时间只要1(因为之前必定以及排序好),否则就要按层次算时间;

代码:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
#define fi first
#define sc second
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define pt(a) cerr<<a<<"---
"
#define rp(i,n) for(int i=0;i<n;i++)
#define rpn(i,n) for(int i=1;i<=n;i++)
const int maxn=1e5+5;
int n,m;
int a[maxn],b[maxn],f[maxn];
void solve(){
	ll ans=0; int pos=-1;
	for(int i=0;i<m;i++){
		if(f[b[i]]>pos) ans+=2ll*(f[b[i]]-i)+1,pos=f[b[i]];
		else ans++;
	}
	cout<<ans<<'
';
}
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin>>t;
	while(t--){
		cin>>n>>m;
		rp(i,n) cin>>a[i],f[a[i]]=i;
		rp(i,m) cin>>b[i];
		solve();
	}
	return 0;
}
原文地址:https://www.cnblogs.com/yuhan-blog/p/12308716.html