[S-Contest] 20181023-T1-排队出发(贪心/排序)

2018-10-24

本文总共 1.4k字 | 你数一下对不对

题目描述

神牛岛是传说中的一个岛屿，凡是成功到那里游历，完成探险并返回的人，都会成为神牛。但是，现实中却没有人知道如何到达神牛岛。
这天夜里，笃志者睡着之后，不久就进入了梦乡。他突然看到有人在问，“有人想去神牛岛的吗？”神牛岛之旅的牌子前，就开始有不少勇士报名要去冒险探索。
“我们会把勇士安排在前，带领大家一起去神牛岛。下面开始点名！”管理队伍的LXY神牛说。其实说实话，给学生排队这种工作是最让神牛头疼的了。因为同学们都有自尊心，都不愿意排后面。共有n个同学要排成一列，每个同学有两个属性：影响力和承受能力。给一个同学造成的心理创伤指数等于所有在他前面同学的影响力之和减去他的承受能力。现在请你帮忙安排一下点名顺序，尽量使受到心理创伤最大的同学少受创伤。

输入&输出细则

【输入】输入文件1.in包含n+1行：
第1行是整数n，表示同学的个数。
第2~n+1行每行两个自然数，分别是该同学的影响力和承受能力。

【输出】输出文件1.out包含1行，为你安排的顺序中受到心理创伤最大的同学受到的创伤。

输入输出样例：

INPUT:
3  
10 3  
2 5  
3 3  
OUTPUT:
2

【数据规模】对于100％的数据，1<=n<=50000，1<=影响力<=10000，1<=承受能力<=1,000,000,000。

题解

没错这就是一道简单的贪心。而且理解起来并不麻烦。我们规定$a_i$表示第i个人的影响力，$b_i$表示第i个人的承受能力。不难发现，这道题~~我所知道~~的最优思路就是先对这组数据进行排序，而排序的方式必定与$a_i$和$b_i$有着某种玄学联系。之后，对排序好的数据进行贪心运算即可。
题目的数据无法保证单调性，所以二分和二分答案是难以实现的。 –By DPair
题目数据不保证无后效性，所以动规是难以实现的。
于是，我们可以得到这道题的基础模板：

for(i=0;i<n;i++)	cin>>a[i]>>b[i];
for(i=0;i<n;i++)	index[i]=1;//index表示元素在序列中排在第几位
sort(index.index+n,cmp);
ans=-INF;tmp=0;
for(i=0;i<n;i++){
    ans=max(ans,tmp-b[index[i]]);
    tmp+=a[index[i]];
}

当然，以上这段用结构体来表示更容易理解。
那么我们只要来简单推一下cmp的内容即可。
由题目可得，对于相邻两个数i，j，他们的先后顺序对其后面的数不造成影响。

不论是i在前还是j在前，他们的影响度总和都是$a_i+b_i$

由题意可得，影响力越大排名越靠后，承受能力越小排名越靠前。为了把这两个量统一考虑，我们单独考虑ij两人中排序后两人靠后的那个人心理创伤指数的大小，并以此作为排序因子。

1
2
3

int cmp(int i,int j){
    return a[i]-b[j]<a[j]-b[i];
}

由此完成。源码不供。

蹲坑记

以上思路全部都是在看过我们同学@DPair同学的题解后写出的，相当于复述。但是事实上一开始我的思路并不是如此。并且，在经过几位大佬的帮助下，我逐渐清晰了自己的思路。
我们规定$a_i$表示第i个人的影响力，$b_i$表示第i个人的承受能力，$Q_i$表示第i个人当前排序情况下的心理创伤指数。设$sum_i$为第1~i个人的影响力之和。勒令第i个人与第j个人相邻。

当i在j前时：
$Q_i = sum_{i-1} - b_i$
$Q_j = sum_{i-1} + a_i - b_j$
当j在i前时：
$Q_i = sum_{i-1} + a_j - b_i$
$Q_j = sum_{i-1} - b_j$

而我们现在需要的是其中的最大值，那么便是：
$max ( Q_i,Q_j )$其中包含以上罗列的$Q_i$和$Q_j$的两种不同情况
提取出$sum_{i-1}$可得到最大值即为：
$max( -b_i , a_i -b_j , -b_j , a_j-b_i )+sum_{i-1}$

此时，我们假设i排在j前面
不难得到，此时两人中心理创伤指数最大值即为：
$max ( Q_i, Q_j ) $
$= max ( sum_{i-1}-b_i,sum_{i-1}+a_i-b_j ) $
$= max ( -b_i,a_i-b_j ) +sum_{i-1} $
我们不妨把max内的两数都加上$b_i+b_j$，然后在max外减去，不难得出
$max ( b_j,a_i+b_i )-b_i-b_j+sum_{i-1} $

当$a_i+b_i>a_j+b_j$时
得到$a_i+b_i>b_j$,最大值为$a_i+b_i$
由于此时$a_i+b_i$是$a_i+b_i$,$a_j+b_j,b_i,b_j$中最大的，所以此时受到伤害最大
当$a_i+b_i<a_j+b_j$时
最大值为$a_i+b_i或b_j$。
而这个值必然小于$a_j+b_j$。
所以我们让$a_i+b_i<a_j+b_j$能比让$a_i+b_i>a_j+b_j$得到更优的解。

于是我们可以得出排序基准：a[i]+[i]<a[j]+b[j]
于是得到排序函数为：

1
2
3

int cmp(int i,int j){
    return a[i]+b[i]<a[j]+b[j];
}

观察一下不难发现其实它和a[i]-b[j]<a[j]-b[i]完全没有区别，但是它们的推导过程大相径庭。

感谢@Onglu的帮助。