T125627 宿命印记题解
一、题目在说什么？
有 NNN 个战士。
第 iii 个战士有一个数字 AiA_iAi 。
如果让他负责攻击，那么他能提供：
AiA_i Ai
点攻击力。
如果让他负责防御，那么他能提供：
1000−Ai1000-A_i 1000−Ai
点防御力。
每个战士只能选择一种工作：
* 要么攻击；
* 要么防御。
最后，军团的总评分为：
总攻击力×总防御力总攻击力\times总防御力 总攻击力×总防御力
我们的任务，就是安排每个人负责攻击还是防御，使这个乘积尽可能大。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、先看一个小例子
假设有两个战士：
A=[4,5]A=[4,5] A=[4,5]
如果让 555 攻击、444 防御：
* 总攻击力是 555；
* 总防御力是 1000−4=9961000-4=9961000−4=996。
评分为：
5×996=49805\times996=4980 5×996=4980
如果反过来，让 444 攻击、555 防御：
* 总攻击力是 444；
* 总防御力是 1000−5=9951000-5=9951000−5=995。
评分为：
4×995=39804\times995=3980 4×995=3980
显然，第一种更好。
这说明：
> 数字较大的战士更适合攻击，数字较小的战士更适合防御。
为什么呢？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、用“分工作”来理解
可以把每个战士想象成一个同学。
每个同学都有两种能力：
* 冲锋能力：AiA_iAi ；
* 守城能力：1000−Ai1000-A_i1000−Ai 。
如果一个同学的 AiA_iAi 很大，说明他冲锋很厉害。
同时，因为他的守城能力是 1000−Ai1000-A_i1000−Ai ，所以他的守城能力会比较小。
例如：
AiA_iAi 攻击能力 防御能力 101010 101010 990990990 900900900 900900900 100100100
所以：
* AiA_iAi 小的人，适合防御；
* AiA_iAi 大的人，适合攻击。
就像安排拔河比赛一样：
* 力气大的同学站在前面拉；
* 比较稳的同学留在后面守。
不能把最有力气的人安排去守门，却让力气较小的人去冲锋。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、为什么“大数攻击，小数防御”一定更好？
假设现在有两个人：
* 小明的数字是 xxx；
* 小刚的数字是 yyy；
* 并且 x<yx<yx<y。
可是现在却安排成：
* 小明，也就是较小的 xxx，负责攻击；
* 小刚，也就是较大的 yyy，负责防御。
这个安排有点不合理。
我们把他们的工作交换一下：
* 让较大的 yyy 去攻击；
* 让较小的 xxx 去防御。
攻击力会发生什么变化？
原来攻击者贡献 xxx，交换后贡献 yyy。
攻击力增加了：
y−xy-x y−x
防御力会发生什么变化？
原来 yyy 负责防御，贡献：
1000−y1000-y 1000−y
交换后，xxx 负责防御，贡献：
1000−x1000-x 1000−x
防御力也增加了：
(1000−x)−(1000−y)=y−x(1000-x)-(1000-y)=y-x (1000−x)−(1000−y)=y−x
也就是说，交换以后：
* 总攻击力变大；
* 总防御力也变大。
两个数都变大，它们的乘积当然也会变大。
所以最优方案里一定不会出现：
> 小数字负责攻击，大数字负责防御。
因此，正确安排一定是：
> 小数字全部防御，大数字全部攻击。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、排序后只需要找一条分界线
我们先把所有 AiA_iAi 从小到大排序。
例如：
1, 2, 3, 7, 91,\ 2,\ 3,\ 7,\ 9 1, 2, 3, 7, 9
最优方案一定长这样：
也可能是：
或者：
我们只需要枚举中间的分界线放在哪里。
这就像老师按照身高排队以后，决定：
> 分界线左边的同学负责防御，右边的同学负责攻击。
不需要再一个一个随便安排。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、怎样快速计算每条分界线的评分？
假设排序后为：
a1≤a2≤⋯≤ana_1\le a_2\le\cdots\le a_n a1 ≤a2 ≤⋯≤an
我们让前 iii 个人负责防御，后面的人负责攻击。
例如：
先计算所有数字的总和：
sum=a1+a2+⋯+ansum=a_1+a_2+\cdots+a_n sum=a1 +a2 +⋯+an
再计算前 iii 个数字的和：
pre=a1+a2+⋯+aipre=a_1+a_2+\cdots+a_i pre=a1 +a2 +⋯+ai
1. 总攻击力
负责攻击的是后面的人。
所以攻击力为：
sum−presum-pre sum−pre
2. 总防御力
前 iii 个人负责防御。
每个人的防御力是：
1000−aj1000-a_j 1000−aj
所以总防御力为：
(1000−a1)+(1000−a2)+⋯+(1000−ai)(1000-a_1)+(1000-a_2)+\cdots+(1000-a_i) (1000−a1 )+(1000−a2 )+⋯+(1000−ai )
一共有 iii 个 100010001000，因此：
总防御力=1000i−pre总防御力=1000i-pre 总防御力=1000i−pre
3. 当前评分
所以当前分界线的评分为：
(sum−pre)×(1000i−pre)(sum-pre)\times(1000i-pre) (sum−pre)×(1000i−pre)
枚举所有分界线，取最大的评分即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、样例解释
数组为：
[1,2,3][1,2,3] [1,2,3]
排序后仍然是：
[1,2,3][1,2,3] [1,2,3]
所有数字之和为：
sum=1+2+3=6sum=1+2+3=6 sum=1+2+3=6
分界线放在第一个人后面
安排为：
前缀和：
pre=1pre=1 pre=1
攻击力：
6−1=56-1=5 6−1=5
防御力：
1000×1−1=9991000\times1-1=999 1000×1−1=999
评分：
5×999=49955\times999=4995 5×999=4995
分界线放在第二个人后面
安排为：
前缀和：
pre=1+2=3pre=1+2=3 pre=1+2=3
攻击力：
6−3=36-3=3 6−3=3
防御力：
1000×2−3=19971000\times2-3=1997 1000×2−3=1997
评分：
3×1997=59913\times1997=5991 3×1997=5991
所以最大答案是：
59915991 5991
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、完整代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、代码每一部分在做什么？
1. 读入并求总和
sum 表示所有 AiA_iAi 的总和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 排序
排序以后：
* 小数字在前面；
* 大数字在后面。
这样就可以让前面的人防御，后面的人攻击。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 枚举分界线
这里的 iii 表示：
> 前 iii 个人负责防御。
因为至少要有一个人防御，也至少要有一个人攻击，所以：
1≤i<n1\le i<n 1≤i<n
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 更新前缀和
pre 表示前 iii 个人的 AiA_iAi 之和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 计算攻击力和防御力
攻击力：
sum−presum-pre sum−pre
防御力：
1000i−pre1000i-pre 1000i−pre
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 更新答案
比较每一种分界线的评分，留下最大的一个。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、为什么要用 LONG LONG？
最多有 100001000010000 个人。
攻击力和防御力都可能接近：
10000×1000=1000000010000\times1000=10000000 10000×1000=10000000
它们的乘积可能接近：
10000000×10000000=10000000000000010000000\times10000000=100000000000000 10000000×10000000=100000000000000
这个数字非常大，int 装不下。
所以必须使用：
代码中写：
也是为了让计算使用 long long，避免溢出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、时间复杂度
排序需要：
O(NlogN)O(N\log N) O(NlogN)
枚举分界线需要：
O(N)O(N) O(N)
所以总时间复杂度为：
O(NlogN)O(N\log N) O(NlogN)
对于 N≤10000N\le10000N≤10000，完全可以通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十二、总结
这道题最重要的想法是：
> 数字小的人适合防御，数字大的人适合攻击。
因此我们先排序，然后枚举一条分界线：
对于每条分界线：
* 攻击力为 sum−presum-presum−pre；
* 防御力为 1000i−pre1000i-pre1000i−pre；
* 评分为两者的乘积。
最后取最大值即可。
可以把整道题记成一句话：
> 先排队，再切一刀，左边防御，右边攻击。
