Posted on 2008-07-19 17:36
crazygir1 阅读(115)
评论(0) 编辑 收藏 引用
#include
#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
posts - 1, comments - 0, trackbacks - 0, articles - 1
Copyright © crazygir1