题意:
给你一个\(n\)元环,你可以在0时刻从任意一个位置出发,每一秒可以选择往后或者留在原地
每个点有个参数\(T_i\),当你走到\(i\)的时间\(t>=T_i\)时你就可以把i标记
问你把整个环上的点都标记最小需要多长时间,带修改\(T_i\),强制在线
好难的题。
首先,有等待操作不太好弄。
可以发现:在总时间一定的情况下,到每个点越晚越好。
所以,可以把所有等待都移到起点处,解不会变差。
由于是环,破环为链处理。
如果在\(s\)时间在\(i (1<=i<=n)\)出发,那么到\(j (i<=j<i+n)\)的时间为\(s+(j-i)\)。根据要求,得\(s+(j-i)>=T_j\),即\(s=max(T_j-j)+i (i<=j<i+n)\)。总时间为\(max(T_j-j)+i+n-1 (i<=j<i+n)\)。