233nmn

题目：题意：分析：代码：

---

题目：

传送门

---

题意：

给出$n$个木材，各自的重量和下一个木材之间的距离 在最后一个位置设有木材厂，同时我们也可以自己设置两个木材厂在任意位置，所有木材只会向编号大的方向移动，直到第一个木材厂为止，花费为移动距离$\ast$重量 问最少花费和是多少，在两个地方设木材厂能做到

---

分析：

模拟退火真是$xswl$ 首先分析下花费的求法，假设$a,b$表示两个木材厂的位置，就有$={\sum }_{i=1}^a{w}_i\ast |a-i|+{\sum }_{i=a+1}^b{w}_i\ast |b-i|+{\sum }_{i=b+1}^n{w}_i\ast |n-i|$ 再设$d_i$表示$1\sim i-1$的距离，用下乘法分配律可以转换成这个亚子： $$d_a\ast \sum _{i=1}^a{w}_i+d_b\ast \sum _{i=a+1}^b{w}_i+d_{n+1}\ast \sum _{i=b+1}^n{w}_i-\sum _{i=1}^n{w}_i\ast d_i$$ 所有考虑把$w$和$d$用前缀和搞出来，而$a,b$用模拟退火一位位移算下就$ojbk$了 比较特殊的是$t_{last}$是无限趋近与$0.5$的就够了，因为当$t$在$0.5$以下时对新的$a,b$是不会有影响的，可以，但没必要

---

代码：

#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstdlib> #include<ctime> #define LL long long #define down 0.99 using namespace std; inline LL read() { LL d=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();} return d*f; } LL n=read(); LL w[20005],d[20005],s; struct qwq{ LL a,b; LL get() { if(a>b) swap(a,b); return w[a]*d[a]+(w[b]-w[a])*d[b]+(w[n]-w[b])*d[n+1]-s; } }best,now,odd; void sa() { double t=n; odd.a=rand()%n+1; odd.b=rand()%n+1; while(t>0.5) { int aa=round((2.0*rand()/RAND_MAX-1)*t); int bb=round((2.0*rand()/RAND_MAX-1)*t); now.a=(odd.a+aa+n)%n+1; now.b=(odd.b+bb+n)%n+1; LL dif=now.get()-odd.get(); if(dif<0) odd=now; else if(exp(-dif/t)*RAND_MAX>rand()) odd=now; if(best.get()>odd.get()) best=odd; t*=down; } return; } int main() { srand(19260817); for(LL i=1;i<=n;i++) { LL a=read(),b=read(); w[i]=w[i-1]+a;d[i+1]=d[i]+b; s+=a*d[i]; } best.a=1;best.b=2; for(int i=1;i<=233;i++) sa(); cout<<best.get(); return 0; }