C. Bricks and Bags Codeforces Round #831 (Div. 1 + Div. 2)

 在经历了几天的卡题和没思路+看题解没看懂中终于把这一道题给磕了出来，感觉这题做不出的原因的没有想好极值的处理关系和太看重特殊情况而忽略了一般情况。。。。。

传送门

题目

有A和B两个人，

给你n个石头和3个袋子w1,w2,w3，，每个石头都有自己的值。现在将所有的石头分装到这三个袋子中，并且保证每个袋子都至少有一个石头。之后a会从这三个袋子中取三个石头，分别代表a，b，c，他的目的是将|a-b|+|b-c|的取值最小化。

现在你是B，问你怎么分配这些石头，使a取到的值最大化。

思路

首先对于a,b,c拿出来的三块石头

那么他们的大小关系只有四种情况 （无论怎么拿）

{a<b<ca>b>cmax(a,c)<bmin(a,c)>b" role="presentation">⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪a<b<ca>b>cmax(a,c)<bmin(a,c)>b$\{\begin{array}{cccc}& & & \\ a<b<c& & & \\ a>b>c& & & \\ max(a,c)<b& & & \\ min(a,c)>b\end{array}$

首先对于第一种结果为c-b+b-a=c-a一定小于等于max-min的，如果是第二种就为a-b+b-c=a-c也是小于等于max-min的，

然后对于第三种，因为b大于w1和w3中的所有的石头，那么b一定为最大的值。

让我们判断一种特殊的情况，w2中只有最大值，w3只有最小值，

那么结果是 max-min+max-max_2，这个结果一定是大于等于第1，2中情况的。

同理，对于第四种，因为b小于w1和w3中的所有的石头，那么b一定是最小 的值

还是进行一个特殊的结果的判断，w2中只有最小的，w1只有最大值，

那么结果是max-min+min_2-min,这个结果也是大于等于第1，2中情况的。

那么我们就只考虑第三，第四种情况：

对于第三种，

我们发现这一种特殊情况不一定是最优的分配情况（！！不一定，我在这里就卡了特别久），就比如下图（横坐标的1，2，3分别代表袋子w1,w2,w3，纵坐标代表石头的值）。

 

 当前是我刚刚上面说的特殊情况，结果是11-2+11-9=11.

如果我把第三袋的最大值的石头放到第二袋中

 结果是9-2+9-4=12，看，是不是比上面的情况要更优。

那么我们可以第一袋是min，第二袋是max，第三袋是剩下的，然后不断把第三袋的max放到第二袋中然后更新max，（别问问什么不放到第一袋，放到第一袋你的值不是铁变小吗！！左边的值和上次右边的值相同，右边的也不能变到min）

那么式子就是

for(int i=n;i>=3;i--)res=max(res,s[i]-s[1]+s[i]-s[i-1]);

 从n到3表示每次拿i的后缀和的石子（当然首先记得排序一下），那么w2的最大值就是s[i]，w3的最大值就是s[i-1]，因为每一袋中至少有一个石头，所以是不能拿到2的。

对于第四种也是一个道理，（把第三袋中最小的放到第二袋中）这里就不多赘述了，直接贴公式

for(int i=1;i<=n-2;i++)res=max(res,s[n]-s[i]+s[i+1]-s[i]);

从1到n-2表示拿i的前缀和的石子，那么w2最小值就是s[i]，w3的最小值是s[i+1].

i<=n-2也是为了保证每一袋中至少有一个石头。

代码

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　	　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/
 
#include
#include 
#include 
#include 
#include 
#include 
#include
#include
#include
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long 
using namespace std;
 
const int N=1000000+100;
int n ,m,h;
ll s[N];
 
 
 
int main()
{
	int t;
	sc_int(t);
	while(t--)
	{
		sc_int(n);
		for(int i =1;i<=n;i++)
		cin>>s[i];
		ll res=0;
		sort(s+1,s+1+n);
		for(int i=n;i>=3;i--)res=max(res,s[i]-s[1]+s[i]-s[i-1]);//最小值放最右边
		for(int i=1;i<=n-2;i++)res=max(res,s[n]-s[i]+s[i+1]-s[i]);//最大值放最右边
		cout<
	}
	return 0;
}

到这里就结束了，尽可能的把自己的思路说的最清晰，只是为了以后如果有我这样不会的题目有一篇适合自己的题解qwq。