建设校园网站国外研究现状,怎么把源码做网站,公司制作网站价格,网站建设兆金手指花总正题
题目链接:https://jzoj.net/senior/#main/show/3832 题目大意
一个环形的#xff0c;知道每个城市分布的位置和需要的酒数。然后要求在一个位置建厂使得运输价格最低。 解题思路
我们将数据复制一份放到后面#xff0c;然后枚举建厂位置。我们现在要找到一个包含该位…正题
题目链接:https://jzoj.net/senior/#main/show/3832 题目大意
一个环形的知道每个城市分布的位置和需要的酒数。然后要求在一个位置建厂使得运输价格最低。 解题思路
我们将数据复制一份放到后面然后枚举建厂位置。我们现在要找到一个包含该位置的长度为nnn的区间使得价格最低。我们发现当建厂位置往右边移动时区间的位置不会向左所以我们可以用指针维护即可。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N41000;
ll n,w[N],d[N],x[N],lw,rw,ans,maxs1e18;
int main()
{//freopen(bro.in,r,stdin);//freopen(bro.out,w,stdout);scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld,w[i],d[i]);x[i]x[i-1]d[i-1];rww[i];answ[i]*x[i];w[in]w[i];d[in]d[i];}for(ll in1;i2*n;i)x[i]x[i-1]d[i-1];ll l1,rn1;for(ll i1;i2*n;i){lww[i-1];rw-w[i];anslw*d[i-1]-rw*d[i-1]-w[i]*d[i-1];while(r2*n(x[i]-x[l])*w[l](x[r]-x[i])*w[r])ans(x[r]-x[i])*w[r]-(x[i]-x[l])*w[l],lw-w[l],rww[r];maxsmin(maxs,ans);}printf(%lld,maxs);
}
