J - 屠龙勇者ErvinXie

本文主要是介绍J - 屠龙勇者ErvinXie，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

已知这个世界中一共有 k 种炼金材料，分别使用 1, 2, 3…k 编号。
炼金法阵的布置方法是将相应炼金材料按直线摆放就能成功布置。法阵一共需要 s 个炼金材料, 法阵
的布置方法通过 a1, a2, a3 · · · as 给出，其中 ai 代表的是炼金材料种类。可能存在不同位置需要摆放相同
种类炼金材料的情况。那么这种材料就需要收集多个。
季蒜脊河的长度为 len, 从源头开始直到末尾，每米存在的炼金材料为 b1, b2, b3 · · · blen。bi 是炼金材
料的种类。
问 ErvinXie 至少需要经过多少个炼金材料（包含收集的）才能去屠龙拯救公主。当然，如果 ErvinXie
注定收集不全材料，他仍然会去拯救公主，和公主在一起… 即使是以恶龙的身份。
例如：季蒜脊河 5 米长，材料为 [1, 2, 1, 3, 2], 法阵的布置方法为 [1, 2, 3, 2]，那么 ErvinXie 可以直接
传送到河里的第 2 个位置，往后收集材料，最终按照顺序收集了 [2, 1, 3, 2] 材料后，能够完成法阵，此时
传送去恶龙谷拯救公主。经过了 4 个炼金材料.
PS：不会吧不会吧，你不会认为 ErvinXie 会按收集顺序摆放法阵吧？ErvinXie 只是懒，不是蠢。他
当然知道材料收集够了，摆放可以自己按顺序摆。

尺取法：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#define ll long long
using namespace std;
const int N = 2e6+10;
unordered_map<int,int>mp;
int num[5005],vis[5005];int main() {int k,s,a[N],len,b[N];scanf("%d",&k);scanf("%d",&s);int cnt=0;for(int i=1; i<=s; i++){scanf("%d",&a[i]);if(num[a[i]]==0)cnt++;num[a[i]]++;}scanf("%d",&len);for(int i=1; i<=len; i++)scanf("%d",&b[i]);int l,r;l = r = 1;int sum=0,ans = N;while(true){while(r<=len&&sum<cnt){vis[b[r]]++;if(vis[b[r]]==num[b[r]])sum++;r++;}if(sum<cnt)break;ans = min(ans,r-l);vis[b[l]]--;if(num[b[l]]>vis[b[l]])sum--;l++;}if(ans==N)printf("DragonXie\n");elseprintf("%d\n",ans);return 0;
}

这篇关于J - 屠龙勇者ErvinXie的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---