[POJ 2886]

Who Gets the Most Candies?

还是线段树……题目是N个人站成一个环进行N轮的筛人,每轮都筛走一个人,第i轮筛走的人得到f(i)颗糖,要求最先得到最多糖的人。第一个被筛的人为k,每次某人被筛,都会给出下一个被筛的人相对当前位置的偏移量(顺时针方向)ai,ai!=0且|ai|<10^8。 其实知道要用线段树之后,题目就很简单了……k值的维护可以通过剩余人数n-i和a[i]求出,然后每轮筛去还在环中的第k个人即可,用线段树可以log(n)得到每轮被筛的人的编号。但这题竟然卡的是求f(i)。。。换了两种方法求f(i)都超时后便老老实实打表了。。。