列表

详情

NC207704. 清理杂物

描述

天空度假山庄里的物品实在是太多了，Madeline想要帮Oshiro先生清理这些物品。

但物品对于未来而言都是可能有用的。

于是Madeline想出了一个方法，给每一个物品定义一个优先级，如果某个物品的最近使用过，那么它的优先级就更高。例如有两个物品，一个物品A在之前使用过，另一个物品B在物品A最后一次使用之后都没有使用过，那么物品A的优先级就比物品B的优先级高。

天空度假山庄的容量是有限的，只能存放个物品，那么优先级前大的物品就会被留下，而优先级比第个物品优先级还要小的物品就会被扔掉。如果被扔掉的物品或者本来就没有的物品想要使用的话，就需要将物品购买回来使用。

一开始天空度假山庄中有个物品，以及每一个物品的编号a_i和每一个物品的优先级的相对顺序。接下来的天，每一天会使用一个编号为b_i的物品，你需要知道这一个物品是否需要购买。

输入描述

输入第一行三个整数、、（），表示一开始天空度假山庄的物品数量、天空度假山庄能存放物品的数量以及需要询问的天数。

第二行输入个整数a_i（），第个数表示一开始天空度假山庄所存在的物品的编号。输入的顺序是按照优先级递增的。即令c_i为一开始第个物品的优先级，则对于所有，有。保证所有的a_i都不相同。

第三行输入个整数b_i（），第个数表示第天使用的物品的编号。

输出描述

第行输出第天使用的编号为b_i的物品是否需要购买。若需要则输出yes，否则输出no。

示例1

输入: 

1 2 10
66
66 64 1 64 3 4 66 6 64 8

输出: 

no
yes
yes
no
yes
yes
yes
yes
yes
yes

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4710ms, 内存消耗: 98060K, 提交时间: 2020-07-19 21:58:41 

#include<map>
#include<iostream>
using namespace std;
int main() {
	map<int, int> con,con2;
	int n, m, q;
	cin >> n >> m >> q;
	int a, i = 1;
	for (; i < n+1; i++) {
		scanf("%d",&a); con[i] = a; con2[a] = i;
	}
	int b;
	for (int j = 0; j < q; j++) {
		scanf("%d", &b);
		if (con2[b] == 0)
			printf("yes\n");
		else {
			printf("no\n");
			con.erase(con2[b]);
		}
		con[++i] = b;
		con2[b] = i;
		if (con.size() > m) {
			con2.erase(con.begin()->second);
			con.erase(con.begin());
		}
	}
}

C++(clang++11) 解法, 执行用时: 2281ms, 内存消耗: 50692K, 提交时间: 2021-03-12 16:30:08 

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
queue <int> nzk;
int bbb[10000005];
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		bbb[x]++;
		nzk.push(x);
	}
	for(int i=1;i<=q;i++)
	{
		int t;
		cin>>t;
		nzk.push(t);
		bbb[t]++;
		if(bbb[t]>1)
		cout<<"no"<<'\n';
		else
		{
			cout<<"yes"<<'\n';
			n++;
			while(n>m)
			{
				bbb[nzk.front()]--;
			if(!bbb[nzk.front()])
			n--;
			nzk.pop();
		}
		}
	}
}

上一题

© 2024 nowcoder.com