这个题耗了我六天时间,很打击我对算法的学习,不过,我终于解决了他。分析如下
仔细观察我们可以发现后面的操作与输出都是围绕标题(title)展开的,作者(author)所起的作用不过是排序而已。我们还注意到一个有趣的地方,即书籍上架时实现排序在上架,那么我们完全可以认为如果能确定一本书的状态的话,我们直接从前往后扫过去就可以了。状态的确定难不难呢?我觉得不难,由题意知每本书有三种状态(已上架、借出、归还但未上架),所以我们可以在定义个变量state记录这三种状态,分别用1、-1、0表示。状态与作者属性都封装在结构体book里,用map与书名形成映射。
书籍上架还有个重要的点要解决,那就是确定书籍的位置。我们可以用扫描法,从当前书籍往前扫,如果有书则输出在这本书后,没书也即j<0时输出该书是第一本书
附上AC代码Time 0ms
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<sstream>
#include<algorithm>
#include<iostream>
using namespace std;
typedef struct book{
int state;
string author;
}book;
const int maxn=200;
char info[maxn];
vector<string> libs;
map<string,book> m;
bool cmp(string s1,string s2)
{
if(m[s1].author!=m[s2].author) return m[s1].author<m[s2].author;
else return s1<s2;
}
void add()
{
stringstream ss(info);
string title="",author="";
string buf;
ss>>buf; title+=buf;
while(ss>>buf){
if(buf=="by") break;
title+=" "; title+=buf;
}
libs.push_back(title);
ss>>buf; author+=buf;
while(ss>>buf){
author+=" "; author+=buf;
}
book b; b.state=1; b.author=author;
m[title]=b;
}
void operate(){
string order,title,buf;
stringstream ss(info);
ss>>order; if(ss>>buf) title+=buf;
while(ss>>buf)
{
title+=" "; title+=buf;
}
switch(order[0])
{
case 'B':{
m[title].state=-1;
break;
}
case 'R' :{
m[title].state=0;
break;
}
case 'S':{
for(int i=0;i<libs.size();i++)
{
title=libs[i];
if(m[title].state!=0) continue;
int j;
for(j=i-1;j>=0;j--)
if(m[libs[j]].state==1) break;
if(j<0) cout<<"Put "<<title<<" first"<<endl;
else cout<<"Put "<<title<<" after "<<libs[j]<<endl;
m[title].state=1;
}
printf("END\n");
break;
}
}
}
int main()
{
while(gets(info) && info[0]!='E' ) add();
sort(libs.begin(),libs.end(),cmp);
while(gets(info) && info[0]!='E') operate();
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)