Code jam 2008 practice A

• A:Saving the universe
• B:Train timetable
• C:Fly swatter

---

A:

The urban legend goes that if you go to the Google homepage and search for “Google”, the universe will implode. We have a secret to share… It is true! Please don’t try it, or tell anyone. All right, maybe not. We are just kidding.

The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine’s name, the universe does implode!

To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they’re received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.

Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.

有很多搜索引擎，當(dāng)請(qǐng)求到某一個(gè)搜索引擎自己的時(shí)候，就會(huì)發(fā)生崩潰，所以需要很好的調(diào)度這些搜索引擎。現(xiàn)在將所有的搜索引擎都放在一起，彼此服務(wù)器之間可以相互指定，這時(shí)候就發(fā)生了交換。現(xiàn)在給出例子和數(shù)據(jù)集，需要給出解決方案，計(jì)算在滿(mǎn)足請(qǐng)求的情況下，最少發(fā)生了幾次服務(wù)器之間的交換。

• 輸入：
  第一行是測(cè)試樣例的數(shù)量
  第二行是搜索引擎的數(shù)量
  接下來(lái)是對(duì)應(yīng)的搜索引擎名字
  再接著是請(qǐng)求的數(shù)量
  最后是對(duì)應(yīng)的具體的請(qǐng)求的名字
• 輸出：
  對(duì)于每一個(gè)測(cè)試樣例，格式如下：
  case #x:y
  表示的是對(duì)于第x個(gè)樣例，發(fā)生了y次交換

分析

把所有的對(duì)于服務(wù)器的請(qǐng)求進(jìn)行分段，要求被分段的請(qǐng)求不包含已經(jīng)給定了的所有的服務(wù)器，否則包含了所有的服務(wù)器之后，就需要發(fā)生交換。這里用到了貪心算法的思想。

代碼

import os os.system('cls')# solution函數(shù)每次解決單個(gè)測(cè)試樣例 def solution(a):# 每次讀取一行，讀取完畢測(cè)試樣例的數(shù)量之后，立即使用readline讀取搜索引擎的數(shù)量即可search_engine_num = int(a.readline())# print(search_engine_num, end=" ")switch_num = 0i = 1# 只需要知道搜索引擎的數(shù)量即可，這里利用readline跳過(guò)搜索引擎，方便繼續(xù)讀取while i <= search_engine_num:a.readline()i += 1query_num = int(a.readline())query_seg = {}for i in range(query_num):query = str(a.readline().strip('\n'))if query_seg.get(query, 0) == 0:# 長(zhǎng)度再增加勢(shì)必引起崩潰，必須開(kāi)始交換if len(query_seg) == search_engine_num - 1:switch_num += 1query_seg.clear()# 判斷用了長(zhǎng)度減一，將會(huì)跳過(guò)下一個(gè)搜索引擎，所以把被忽略的一個(gè)引擎添加到請(qǐng)求的段中query_seg[query] = 1return switch_num# infile = open("A-small-practice.in", "r") infile = open("A-large-practice.in", "r") caseNum = int(infile.readline()) result = [] flag = 1 # os.remove('test_result.txt') if os.path.exists("A_large_result.out"):os.remove("A_large_result.out") while flag <= caseNum:switch_num = solution(infile)print("Case #", flag, ":", switch_num)with open("A_large_result.out", 'a') as f:f.writelines(["Case #", str(flag), ": ", str(switch_num), "\n"])f.closeflag += 1

結(jié)果 (大數(shù)據(jù)集)：

Case #1: 0 Case #2: 0 Case #3: 1 Case #4: 1 Case #5: 3 Case #6: 3 Case #7: 999 Case #8: 498 Case #9: 12 Case #10: 1 Case #11: 4 Case #12: 1 Case #13: 6 Case #14: 0 Case #15: 1 Case #16: 11 Case #17: 1 Case #18: 3 Case #19: 3 Case #20: 2

總結(jié)

以上是生活随笔為你收集整理的Code jam 2008 practice A的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。