本文主要是介绍hiho一下 第六十二周 题目1 : Browser Caching stl 应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目1 : Browser Caching
-
5 2 www.bing.com www.microsoft.com www.microsoft.com windows.microsoft.com www.bing.com
样例输出 -
Internet Internet Cache Internet Internet
描述
When you browse the Internet, browser usually caches some documents to reduce the time cost of fetching them from remote servers. Let's consider a simplified caching problem. Assume the size of browser's cache can store M pages. When user visits some URL, browser will search it in the cache first. If the page is already cached browser will fetch it from the cache, otherwise browser will fetch it from the Internet and store it in the cache. When the cache is full and browser need to store a new page, the least recently visited page will be discarded.
Now, given a user's browsing history please tell us where did browser fetch the pages, from the cache or the Internet? At the beginning browser's cache is empty.
输入
Line 1: Two integers N(1 <= N <= 20000) and M(1 <= M <= 5000). N is the number of pages visited and M is the cache size.
Line 2~N+1: Each line contains a string consisting of no more than 30 lower letters, digits and dots('.') which is the URL of the page. Different URLs always lead to different pages. For example www.bing.com and bing.com are considered as different pages by browser.
输出
Line 1~N: For each URL in the input, output "Cache" or "Internet".
提示
Pages in the cache before visiting 1st URL [null, null]
Pages in the cache before visiting 2nd URL [www.bing.com(1), null]
Pages in the cache before visiting 3rd URL [www.bing.com(1), www.microsoft.com(2)]
Pages in the cache before visiting 4th URL [www.bing.com(1), www.microsoft.com(3)]
Pages in the cache before visiting 5th URL [windows.microsoft.com(4), www.microsoft.com(3)]
The number in parentheses is the last visiting timestamp of the page.
stl 简单应用。
直接用map维护所有的缓存，如果存在就输出缓存。再用map记录，最近使用的时间，总的复杂度为o(n * log(n));
#define N 205
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
int n,m;
char str[100];
map<string,int> strm;
map<int,string> timem;
map<int,string>::iterator it;
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);while(S2(n,m)!=EOF){strm.clear();timem.clear();FI(n){SS(str);if(strm.count(str)){printf("Cache\n");int t = strm[str];timem.erase(t);strm[str] = i;timem[i] = str;}else{printf("Internet\n");if(timem.size() >= m){it = timem.begin();strm.erase(it->second);timem.erase(it);strm[str] = i;timem[i] = str;}else {strm[str] = i;timem[i] = str;}}}}//fclose(stdin);//fclose(stdout);return 0;
}
这篇关于hiho一下 第六十二周 题目1 : Browser Caching stl 应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
