Day 11.17模拟赛游记

吐槽：连续三天的(duliu)题，第一题签到，后面？？？送命！！

---

T1.cuvelia

一句话题意：求对于每一个(~i~(~i~le~n)),从一个序列中选出(n)个数,使得选出的数两两之差的绝对值最大。

应该挺简单的吧，我们如果把选出来的序列排个序，对于一个位置(~p)，假如他右边有(n)个数，每一个数和它作差的贡献为(a_R~-~a_p)，所以对于(a_p)，它的贡献为(-~n~ imes~a_p)，同理，假如左边有(m)个数，那么这个数总共的贡献为((m-n)~ imes~a_p)。又因越右边的数(m~-~n)越大，所以整个选择的序列为单调不下降，然后对于整个序列在中点右边的数(m~-~n~ge~0)，所以这些数越大越好，左边的数(m~-~n~le~0)，所以选择的数越小越好，因此整个选择的序列一定为原序列排序后的左右两边各(i/2)个。

大致算法就讲完了，然后用前缀和维护就好了。

手起码落，把这题咔嚓了：

#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=300005;
int n,a[N];
long long ans[N][2],sum[N][2];
int main()
{
	scanf("%d",&n);
	for(re int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(re int i=1;i<=n;i++) sum[i][0]=sum[i-1][0]+a[i];
	for(re int i=n;i>0;i--) sum[i][1]=sum[i+1][1]+a[i];
	for(re int i=1;i<=(n>>1);i++)
	{
		ans[i<<1][0]=ans[(i<<1)-1][0]-sum[i][0];
		ans[(i<<1)+1][0]=ans[i<<1][0]-sum[i][0];
	}
	re int mid=(n-1)/2+1;
	for(re int i=n,l;i>mid;i--)
	{
		l=n-i+1;
		ans[l<<1][1]=ans[(l<<1)-1][1]+sum[i][1];
		ans[(l<<1)+1][1]=ans[l<<1][1]+sum[i][1];
	}
	for(re int i=1;i<=n;i++) printf("%lld
",ans[i][0]+ans[i][1]);
	return 0;
}

---

T2？T3？T4？ 咕咕咕~~