题解 P3955 【图书管理员】

sbcxknmsl

2017-11-18 20:53:53

Solution

~~我不会告诉你我没过普及组初赛~~ # 看到这道题总体思路就是:先排序,确保序号较小的在前,然后双重循环,将书的号码和用户要找的号码比较就行了。 然而实际做的时候遇到了很多问题:我用字符串比较书的号码和用户要找的号码,佷麻烦,排序还要使用操作符重载,还要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!!! ```