题意:有一个人有n本书,计划一年之内要读m次书(一本书可以反复读)。这n本书是叠放在一起的,每次读一本书要把上面的书移开,在把书给取走。并且读完之后要把它放在最上面,要你求出读完所有书的最小移动重量。
思路:不管最开始如何放置,最先读的书一定是在后面读的书的上面,所以只能要求在读某一本书的时候后,保证上面的都是读过的书就可以。所以,这也就确定了最开始的排列顺序——按照读书的顺序。然后再统计每次读的时候所移动书的重量就可以了。
#include <map> #include <set> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <iostream> #include <stack> #include <cmath> #include <string> #include <vector> #include <cstdlib> //#include <bits/stdc++.h> //#define LOACL #define space " " using namespace std; //typedef long long LL; //typedef __int64 Int; typedef pair<int, int> paii; const int INF = 0x3f3f3f3f; const double ESP = 1e-5; const double PI = acos(-1.0); const int MOD = 1e9 + 7; const int MAXN = 1e5; int weight[MAXN], pos[MAXN]; int st[MAXN], num[MAXN]; bool vis[MAXN]; int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) { scanf("%d", &weight[i]); } int cnt = 0; for (int i = 0; i < m; i++) { scanf("%d", &st[i]); if (!vis[st[i]]) { pos[cnt++] = st[i]; vis[st[i]] = true; } } int ans = 0; memset(vis, 0, sizeof(vis)); cnt = 0; //遍历每天 for(int i = 0; i < m; i++) { int p; for (p = 0; pos[p] != st[i]; p++) { ans += weight[pos[p]]; } for(int j = p;j >= 1; j--) pos[j] = pos[j - 1]; pos[0] = st[i]; } printf("%d ", ans); } return 0; }