优秀网站建设评选活动海报,软件开发工程师报考条件,WordPress 全局Ajax,容易被百度收录的网站正题 题目大意
若干个长2高1的长方形且有不同的质量。 对于若干个矩形的重心定义为∑mi∗xi∑mi\frac{\sum m_i*x_i}{\sum m_i}∑mi∑mi∗xi 要求每个矩形上面的所有矩形的x重心跟该矩形的x中点相距不超过1。 最底下的矩阵的右下角摆放在(−2,0)(-2,0)(−2,0)的位置求…正题 题目大意
若干个长2高1的长方形且有不同的质量。 对于若干个矩形的重心定义为∑mi∗xi∑mi\frac{\sum m_i*x_i}{\sum m_i}∑mi∑mi∗xi 要求每个矩形上面的所有矩形的x重心跟该矩形的x中点相距不超过1。 最底下的矩阵的右下角摆放在(−2,0)(-2,0)(−2,0)的位置求最上面最右能到多远。 解题思路
我们二分答案然后只要最后重心能到0或以内就可以了。 定义si∑ji1nmjs_i\sum_{ji1}^nm_jsi∑ji1nmj 从上到下摆放先假设第一个摆放到无限远也就是重心G∞G\inftyG∞ 然后首先我们可以计算出如果往最右拜访重心会到达哪里 也就是(G∗simi∗(G−1))/(simi)(G*s_im_i*(G-1))/(s_im_i)(G∗simi∗(G−1))/(simi) 但是如果我们发现这时候已经不可以稳定了也就是 G∗(simi)gt;(lim−2)∗si(lim−1)∗miG*(s_im_i)gt;(lim-2)*s_i(lim-1)*m_iG∗(simi)(lim−2)∗si(lim−1)∗mi 那么我们就整体向左边移动使得 G((lim−2)∗si(lim−1)∗mi)/(simi)G((lim-2)*s_i(lim-1)*m_i)/(s_im_i)G((lim−2)∗si(lim−1)∗mi)/(simi) 时间复杂度O(nlog(n∗106))O(n\ log\ (n*10^6))O(n log (n∗106)) codecodecode
#includecstdio
#includealgorithm
#define ll long long
using namespace std;
const double eps1e-9;
const ll N310000;
ll n,m[N],s[N];
bool check(double lim)
{double G1e9;for(ll in;i2;i--){G(G*s[i]m[i]*(G-1))/(s[i]m[i]);if(G*(s[i]m[i])(lim-2)*s[i](lim-1)*m[i])G((lim-2)*s[i](lim-1)*m[i])/(s[i]m[i]);}return G0;
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,m[i]);for(ll in-1;i;i--)s[i]s[i1]m[i1];double l0,rn;while(r-leps){double mid(rl)/2;if(check(mid)) lmid;else rmid;}printf(%.9lf,l);
}
