几道线性的题目

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的, 但是线性扫描的思路很巧,值得注意.
直接二分更简单,对每对相邻的点,二分查找它们之间是否有线段.