做网站需要简介,网站建设与网页设计考试题,怎么样做问卷网站,影视网站wordpress正题
题目链接:https://ac.nowcoder.com/acm/contest/7413/C 题目大意
给一个序列AAA#xff0c;求两个a,ba,ba,b使得∑i1n∑j1nmax{∣Ai−a∣,∣Aj−b∣}\sum_{i1}^n\sum_{j1}^nmax\{|A_i-a|,|A_j-b|\}i1∑nj1∑nmax{∣Ai−a∣,∣Aj−b∣}最小。 解题思路
因为是取…正题
题目链接:https://ac.nowcoder.com/acm/contest/7413/C 题目大意
给一个序列AAA求两个a,ba,ba,b使得∑i1n∑j1nmax{∣Ai−a∣,∣Aj−b∣}\sum_{i1}^n\sum_{j1}^nmax\{|A_i-a|,|A_j-b|\}i1∑nj1∑nmax{∣Ai−a∣,∣Aj−b∣}最小。 解题思路
因为是取maxmaxmax也就是a,ba,ba,b中最劣的那一个所以显然有ababab。
考虑如和求aaa不难发现其实答案就是对于每个AiAj2\frac{A_iA_j}{2}2AiAj的中位数。我们可以二分答案然后求在midmidmid前有多少个AiAjA_iA_jAiAj这个显然也可以将数组排序后二分求得其实不二分用指针也行。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll XJQ1e97;
ll n,a[110000];
ll find(ll x){ll l1,rn;while(lr){ll mid(lr)1;if(a[mid]x)lmid1;else rmid-1;}return r;
}
ll check(ll mid){ll ans0;for(ll i1;in;i)ansfind(mid-a[i]);return ans;
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]);sort(a1,a1n);ll l1,r1e9,kn*n;while(lr){ll mid(lr)1;if(check(mid)(k1)/2)rmid-1;else lmid1;}ll ans0;for(ll i1;in;i)a[i]abs(a[i]*2-l);sort(a1,a1n);for(ll i1;in;i)ansa[i]*((i-1)*21);printf(%lld,ans%XJQ);
}
