该总结还暂未完成，待日后继续总结……
比赛链接
题解文件
点击下载：月赛决赛.7z
总结范围
- A
- C
- D
- E
- G
- H
- J
- K
注：前面带*号的题因题目简单，为简略总结。
- 其余题目均因时间原因暂未总结。
A - 排队
比赛情况：WA
题面搬运
题面搬运
题目描述
世界任务：是芭芭拉还是⑨⑨拉
班尼特又误伤了自己，现在$n$个班尼特正找芭芭拉治疗。
对于每个班尼特，芭芭拉需要给他补血$h_i$，然后获得一个价值$v_i$的圣遗物。
治疗每一个班尼特都会获得一个收益，治疗第$i$个班尼特的收益$w_i$等于前面治疗的所有班尼特的$v$之和减去$h_i$。
芭芭拉想让治疗每个班尼特收益的最小值最大。
也就是说，请重新给班尼特排队，要求是最大化$\min_{i=1}^n{-h_i+\sum_{j=1}^i v_j}$
，并输出这个值。
芭芭拉并不擅长数学，因此请身为骑士团荣誉骑士的你帮帮她吧。
任务奖励：10个原石，角色芭芭拉，以及月赛增加一个AC
数据范围
$1 \le n \le 10^5$
$1 \le h_i,v_i \le 10^4$
输入格式
第一行有一个整数$n$。
接下来有$n$行，每行有两个数字$h$,$v$，代表这个班尼特的补血量和圣遗物。
输出格式
一行，只有一个整数，代表所有最小值中的最大值。
样例数据
第一组
输入
3
100 200
300 500
400 700
输出
300
解释：
若顺序为($100,200)(300,500)(400,700)$，则收益为$100,400,1000$，最小收益为$100$。
若顺序为$(300,500)(100,200)(400,700)$，则收益为$200,600,1000$，最小收益为$200$。
若顺序为$(400,700)(100,200)(300,500)$，则收益为$300,600,1100$，最小收益为$300$。
还有其它顺序，但最小收益不会超过$300$，因此答案为$300$。
标准思路
- 算法点：贪心——邻项交换排序
它把决定相邻两个元素先后的决策推广到整个序列，从而获得最优解。
这个题本身就是通过给数据排序，不同的排序方法会有不同的收益最小值，然后要比较所有排序方法，选让这个收益最值最大那种方法……
所以排序的话我们就每次选两个人比较，标记为$i$和$j$……
然后这两个人又有两种情况，要不就是$i$站在$j$前面，要不就是$j$站在$i$前面……
这两种情况分别会有个当前两个人的收益最小值，如果目前这种方法（$i$站在$j$前面）的这个最值小于后者方法（$j$站在$i$前面），那肯定我就选后者，让收益最大化，就让他们交换顺序……
就相当于把比较时候的最值看成短板，每次比较一次选最高的那个，就会把短板提上去一点，这样最后得到的就是最高的短板……
用公式来说的话就是$\text{if} \quad (\min(Wi_1,Wj_1) < \min(Wi_2,Wj_2)) \quad \text{swap}((h,v)_i,(h,v)_j)$……
最终分析得知就是if (vi-hi < vj-hj) swap(i,j);……
有关“邻项交换排序”的详细介绍可以查看我的笔记「ACM学习笔记——邻项比较排序……」。
标程代码
标程代码
//理解了就很简单，就不给标程加注释了……
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100010;
struct Data
{
int h, v;
bool operator<(const Data &t) { return v - h > t.v - t.h; }
};
int n;
Data d[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &d[i].h, &d[i].v);
sort(d + 1, d + n + 1);
int tmp = 0, res = 1e9;
for (int i = 1; i <= n; ++i)
{
tmp += d[i].v;
res = min(res, tmp - d[i].h);
}
printf("%d\n", res);
return 0;
}