幾道線性的題目

Tanks a Lot
題意:
一個(gè)圓,周長(zhǎng)為整數(shù)n(n<=10^7).圓周上有k(k<=n)個(gè)加油站,每個(gè)加油站有整數(shù)的油量w[i],所有加油站總油量恰好為n. 行車單位路程耗油量為1, 車的初始油量為0. 問(wèn),以哪些加油站為起點(diǎn)可以走完一周? 分別判斷順時(shí)針和逆時(shí)針的情況.
解:
棧的應(yīng)用.
考慮單個(gè)點(diǎn)v1,沿路徑v1,v2,v3,...走,則從v1能完成一周的充要條件是對(duì)任意的k,S[1,k-1]-C[1,k]>=0,其中S[1,k-1]為這段路上總加油量,C[1,k]為總耗油量.
再考慮先后2個(gè)點(diǎn)vk1,vk2. 設(shè)沿路徑vk1,vp1,vp2,...,vk2,...vpm走.如果vk1和vk2都能到達(dá)vpm,肯定vk1必需先能夠達(dá)到vk2. 這說(shuō)明從vk1到vpm時(shí)的剩余油量肯定>=vk2到vpm時(shí)的剩余油量. 有了這個(gè)單調(diào)性,再加上油余量的區(qū)間性以及區(qū)間可合并性, 就可以維護(hù)一個(gè)單調(diào)的棧.棧中頂點(diǎn)的訪問(wèn)次序遞增,剩余油量遞減且不小于0.正掃一遍反掃一遍分別判斷順時(shí)針和逆時(shí)針.

A Walk in the Park
題意:
二維平面上有一些(N<=10^5)無(wú)限長(zhǎng)的水平線和豎直線(M<=10^5), 以及一些不在線上的點(diǎn). 人可以沿任意線走.
稱某個(gè)點(diǎn)是可見(jiàn)的, 當(dāng)且僅當(dāng)人能站在某條線上, 以垂直于線的方向正對(duì)此點(diǎn),并且人與點(diǎn)的連線上沒(méi)有其它點(diǎn)阻礙視線.
求可見(jiàn)的點(diǎn)的個(gè)數(shù).
解:
排序+離散化+線性掃描; 二分
先考慮能否從水平線上看到某個(gè)點(diǎn).
將點(diǎn)按y坐標(biāo)排序.
對(duì)同一x上的所有點(diǎn),考慮不是起始或末尾的相鄰的兩個(gè)點(diǎn),它們能被看到,當(dāng)且僅當(dāng)它們之間有直線.
這樣可以把直線也按y排序, 順序掃一遍.對(duì)某個(gè)坐標(biāo)x,記錄它上一個(gè)點(diǎn)的y值.
離散化和排序都是nlogn的, 但是線性掃描的思路很巧,值得注意.
直接二分更簡(jiǎn)單,對(duì)每對(duì)相鄰的點(diǎn),二分查找它們之間是否有線段.