题解：P3955 [NOIP2017 普及组] 图书管理员

本题算法为：贪心，取模运算，模拟。

本题解法：

首先我们要知道， $x$ 除以 $10^n$ 的余数可以得到的是这个数 $x$ 的后 $n$ 位。
根据上面这个特性，我们可以先将书的编号从小到大排序，然后每次算出 $10^x$ ，再枚举书的编号，如果找到就直接赋值并退出，否则输出 -1。
再枚举前可以将答案 $ans$ 设为 -1，这样有一个好处：如果没有找到答案就可以直接输出 -1，不需要特判，比较方便。
代码:

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int book[maxn];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>book[i];
	sort(book+1,book+1+n);//因为要找编号较小的，所以从小到大排序
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		int tmp=pow(10,x);//取10^x,取模时会用到
		int ans=-1;//先设为-1,方便处理
		for(int i=1;i<=n;i++)
		{
			if(book[i]%tmp==y)//如果取模后是编号y
			{
				ans=book[i];//直接赋值答案并退出。
				break;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

题解：P3955 [NOIP2017 普及组] 图书管理员

文章操作

相关推荐

评论

题解：P3955 [NOIP2017 普及组] 图书管理员