woj1414 – URL 解题报告
原题目见：Problem 1414 – URL 。
题目的背景是，我们在浏览器中输入URL时，浏览器会提示我们之前搜索过的，URL以当前字符为前缀的的网页，并且按照之前访问次数来递减显示。
思路，每次Visit时将访问的页面作为KEY来保存，并且次数增1。每次Display时，搜索所有现存的网页，找到以当前字符串为前缀的字符串，并按次数逆序输出。
虽然解题报告不提倡直接贴代码，不过我的代码没多少行，题目又比较简单，就给我AC的代码吧。这题的数据比较弱，我看前200多名都是0MS。代码是逼着自己用STL中的容器map写的，如果发现有什么改进的地方请告诉我。
#include <iostream> #include <map> #include <string> using namespace std; int main() { string prompt,str; int n,m; string visit("Visit"); //string display("Display"); typedef map<string , int> Urls; typedef Urls::const_iterator UrlsIter; typedef multimap<int ,string , greater<int> > Urlrank; typedef Urlrank::const_iterator RankIter; Urls url; Urlrank urlrank; cin>>n; while( n-- ){ cin>>m; url.clear(); urlrank.clear(); while( m--){ cin >> prompt >> str; if ( visit.compare(prompt)==0){ url[str]++; }else{ for(UrlsIter iter = url.begin(); iter != url.end(); iter++ ){ string tmp(iter->first); if ( tmp.find(str) == 0 ){ urlrank.insert( make_pair( iter->second,iter->first ) ); } } for( RankIter iter = urlrank.begin(); iter != urlrank.end(); iter++) cout << iter->second <<endl; cout <<endl; urlrank.clear(); } } } return 0; }
看完了^.^,如果觉得这篇文章对你有用或者有
问题,请留言告诉我,thank you !
文章为原创的话,转载请注明出处.不敢流泪-《woj1414 – URL 解题报告》
One Comment
这缩进。。。。。。。。-_-||（突然发现你的表情里面居然没有汗。。）
大概看了下，你的mulitMap完全可以用优先队列来替代，或者一个下标vector进行sort都会更快些。
不过你那个遍历map的操作显然不是最好的方法。
PS：visit.compare(prompt)==0这是太古老的C写法了，可以直接visit == prompt
[回复]
boluor 回复 于 八月 31st, 2009 at 16:06
缩进出现问题原来是我在CB中部分代码是用了TAB符号，部分是TAB用空格代替…现在好了。
看到map和multimap，发现用这两个容器就可以实现了，就没去用vector排序和priority_queue了。我晚上用这两个写下。
[回复]