题解 P3955 【图书管理员】
sbcxknmsl
2017-11-18 20:53:53
~~我不会告诉你我没过普及组初赛~~
# 看到这道题总体思路就是:先排序,确保序号较小的在前,然后双重循环,将书的号码和用户要找的号码比较就行了。
然而实际做的时候遇到了很多问题:我用字符串比较书的号码和用户要找的号码,佷麻烦,排序还要使用操作符重载,还要struct……
具体注释见代码
```cpp
#include<bits/stdc++.h>
using namespace std;
struct str
{
string s;
bool operator < (const str&t)const//操作符重载,防止排序时出问题
{
if(s!=t.s)
{
if(s.length()<t.s.length())return true;
else if(s.length()>t.s.length())return false;
else return s<t.s;
}
}
};
str num[1005];//书的号码
str nu[1005];//用户要找的号码
int main()
{
int a,i,j,k,n,m,b;
cin>>n>>m;
for(i=0;i<n;++i)
{
cin>>num[i].s;
}
for(i=0;i<m;++i)
{
cin>>a>>nu[i].s;
}
sort(num,num+n);
for(i=0;i<m;++i)
{
bool t=false;
a=nu[i].s.length();
for(j=0;j<n;++j)
{
t=false;//注意!要初始化
b=num[j].s.length();
for(k=0;k<=a;++k)
if(nu[i].s[k]!=num[j].s[b-a+k])//比较
t=true;
if(!t)
{
cout<<num[j].s<<endl;//输出
break;
}
}
if(!t)
continue;//找到后做下一个
else
cout<<-1<<endl;//没找到后输出
}
}
```
写完后提交,我过了,然后某神犇跑过来跟我说:你用string比较很慢的,要用int比较
# 使用书的号码减掉要找到号码,如果结尾都是0,就说明它们的结尾相同!!!!!!!!!!重要思路!!!!!
于是我又写了一个
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,i,j,k,n,m,num[1005],cou[1005],number[1005];//num:书的号码 cou:要找的号码 //number:要找号码的位数
cin>>a>>b;
for(i=0;i<a;++i)cin>>num[i];
for(i=0;i<b;++i)cin>>number[i]>>cou[i];
sort(num,num+a);//排序
for(i=0;i<b;++i)
{
bool t=false;
m=10;
for(k=1;k<number[i];++k)
m*=10; //位数
for(j=0;j<a;++j)
{
n=num[j]-cou[i];
if((n%m)==0)//比较
{
t=true;
break;
}
}
if(t)
cout<<num[j]<<endl;//输出
else
cout<<-1<<endl;
}
return 0;
}
0ms!!!
```