幾道線性的題目

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

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