C++博客-Crazygir1's Skyhttp://www.cppblog.com/crazygir1/zh-cnTue, 09 Jun 2026 19:08:43 GMTTue, 09 Jun 2026 19:08:43 GMT60serverhttp://www.cppblog.com/crazygir1/archive/2008/07/19/56613.htmlcrazygir1crazygir1Sat, 19 Jul 2008 09:36:00 GMThttp://www.cppblog.com/crazygir1/archive/2008/07/19/56613.htmlhttp://www.cppblog.com/crazygir1/comments/56613.htmlhttp://www.cppblog.com/crazygir1/archive/2008/07/19/56613.html#Feedback0http://www.cppblog.com/crazygir1/comments/commentRss/56613.htmlhttp://www.cppblog.com/crazygir1/services/trackbacks/56613.html #include #include using namespace std; #define LL long long const int maxn = 1000100; int n; LL cost[maxn],f[maxn]; int q[maxn]; LL catchup[maxn]; int qh,qt; LL GetF(int a,int b) { return f[b]+(LL)(a-b)*(LL)(a-b-1)/2+cost[a]; } int FindCatchup(int a,int b) { // can be implemented as an expression for easier situations int l=b+1,r=n,m; int ret=n+1; while (l<=r) { m=(l+r)/2; if (GetF(m,b)<=GetF(m,a)) { ret=m; r=m-1; } else l=m+1; } return ret; } int main() { int i,j; LL k; freopen("server.in","r",stdin); freopen("server.out","w",stdout); cin>>n; for (int i=1;i<=n;i++) cin>>cost[i]; qh=0;qt=0; q[qh]=0; f[0]=0; for (int i=1;i<=n;i++) { while (qh

crazygir1 2008-07-19 17:36 发表评论
]]>