Acwing蓝桥杯集训·题解 week2
农夫约翰最喜欢的操作分几步来：
[*]要满足\(a_i-x\)整除\(x\)
转化一下为，即满足\(a_i \equiv x \pmod M\) ，所以预处理，\(a_i=a_i \mod M\)
[*]由第一步，我们可以知道\(x\in (0,M-1)\)
[*]根据题意我们所求值 \(val=\sum_{i=1}^{i=n}|a_i-x|\)
当val取最小值时，由于中位数定理，x是序列\(a_i\)的中位数
[*]由于同余的性质，所以\(a_i \equiv a_i+M \pmod M\)
[*]所以x可以取不同的\(a_i\)，就会有不同的序列，因此我们取每一个序列的中位数，比较每个序列的val，取最小
[*]当x取不同的\(a_i\)时，应该以\(a_i\)为中心建立一个序列，通过取余，将两边的\(a\)数量平衡
[*]为了方便这样处理可以\(a_i+M\)个数加到原序列之后，然后用前缀和快速求解
点击查看代码#includeusing namespace std;#define ll long long int n,x,k,m;const int maxn=4e5+10;int t;int w;ll sum; void solve(){ cin>>n>>m; for(int i=1;i>w,w%=m; sort(w+1,w+1+n); for(int i=1;in>>m; int l=1; for(int i=1;i>a; } for(int i=1;i>b; int now=0; for(int j=1;jn; cin>>s; s=" "+s; int r=n; for(int i=1;i
页:
[1]