@[黑影洞人](/user/285617) 优化一下calc
by rabbyte @ 2022-07-21 16:52:02
看能不能O（1）
by rabbyte @ 2022-07-21 16:52:18
@[rabbyte](/user/638235) 优化了，49pts
by 黑影洞人 @ 2022-07-21 16:52:43
@[rabbyte](/user/638235)
改过后的
```cpp
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#define N 114514
#define int long long
using namespace std;
int xxx,yyy,n,w[N],d[N],s[N],ans,fifi,best;
const double eps=1e-12;
int calc(){
return s[xxx]*w[xxx]+s[yyy]*(w[yyy]-w[xxx])+s[n+1]*(w[n]-w[yyy])-fifi;
}
void sa(){
for(double t=1145;t>eps;t*=0.998){
//printf("%d\n",ans);
int x=xxx,y=yyy;
xxx=rand()%n+1;yyy=rand()%n+1;
if(xxx>yyy)swap(xxx,yyy);
int now=calc(),del=now-ans;
if(del<eps)ans=now;
else if(exp(-del/t)*RAND_MAX<rand())xxx=x,yyy=y;
best=min(best,ans);
}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&w[i],&d[i]);
s[i]=s[i-1]+d[i-1];
fifi+=s[i]*w[i];
w[i]+=w[i-1];
}
s[n+1]=s[n]+d[n];
xxx=1,yyy=2;
best=ans=calc();
while((double)clock()/CLOCKS_PER_SEC<=0.67)sa();
printf("%lld",best);
return 0;
}
```
by 黑影洞人 @ 2022-07-21 16:53:26
@[黑影洞人](/user/285617) 代码
by rabbyte @ 2022-07-21 16:53:31
@[黑影洞人](/user/285617) 您不是A了吗（
by rabbyte @ 2022-07-21 16:58:21
@[rabbyte](/user/638235) 我打了个暴力
by 黑影洞人 @ 2022-07-21 21:15:58