P1057 天地皆可往 官方题解

【题意分析】

• 会增加龙威的疆土先处理，能够为后续行程留下更多余量。会减少龙威的疆土放在后面，并按照离开时的门槛安排顺序。

【部分分：测试点 1∼21\sim 21∼2】

• 固定一个前往疆土的排列后，从前向后模拟即可求出完成这个排列所需的最小初始龙威。
• 枚举全部 $n!$ 个排列，取这些排列对应答案的最小值。
• 单次模拟需要 $\mathcal O(n)$ 的时间，总时间复杂度为 $\mathcal O(n!n)$。

【部分分：测试点 3∼53\sim 53∼5】

• 二分初始龙威 $x$。令 $f_S$ 表示已经前往集合 $S$ 中的疆土时，最多能够剩下多少龙威，不可达状态记为负无穷。
• 若 $i\notin S$ 且 $f_S\geq a_i$，则有

• 检查一次需要 $\mathcal O(n2^n)$ 的时间。答案具有单调性，因此可以二分最小的可行 $x$。

【部分分：测试点 6∼106\sim 106∼10】

• 特殊性质 A 保证 $b_i\geq 0$。一旦能够进入某片疆土，完成当地事务后龙威不会下降。
• 因此按照 $a_i$ 从小到大前往一定不劣。若当前能够进入后一片疆土，那么前面的疆土只会继续增加龙威。
• 排序后顺序模拟即可，时间复杂度为 $\mathcal O(n\log n)$。

【部分分：测试点 11∼1511\sim 1511∼15】

• 特殊性质 B 保证 $b_i<0$。考虑相邻的两片疆土 $i,j$。
• 若先去 $i$ 再去 $j$，除了进入 $i$ 需要满足 $x\geq a_i$，进入 $j$ 还需要满足 $x+b_i\geq a_j$。
• 比较两种顺序后可知，应当按照 $a_i+b_i$ 从大到小排列。这个量表示离开疆土 $i$ 时至少能够保留的龙威门槛。
• 排序后顺序模拟，时间复杂度为 $\mathcal O(n\log n)$。

【部分分：测试点 16∼2016\sim 2016∼20】

• 先处理所有 $b_i\geq 0$ 的疆土，再处理所有 $b_i<0$ 的疆土一定不劣。
• 前一部分按照 $a_i$ 从小到大排列，后一部分按照 $a_i+b_i$ 从大到小排列。
• 设已经完成的龙威变化量之和为 $S$。来到疆土 $i$ 前必须有 $\operatorname{Ans}+S\geq a_i$，所以

• 时间复杂度为 $\mathcal O(n\log n)$，空间复杂度为 $\mathcal O(n)$。

【参考代码】

1#include <cstdio>2#include <vector>3#include <algorithm>4#define MAXN 2000105using namespace std;6 7struct land{8    long long Need,Change;9}Line[MAXN];10 11bool Compare(const land &A,const land &B){12    if((A.Change>=0)!=(B.Change>=0)) return A.Change>=0;13    if(A.Change>=0) return A.Need<B.Need;14    return A.Need+A.Change>B.Need+B.Change;15}16 17int main(){18    int c,T,n;19    scanf("%d%d",&c,&T);20    while(T-->0){21        scanf("%d",&n);22        for(int i=1;i<=n;i++) scanf("%lld%lld",&Line[i].Need,&Line[i].Change);23        sort(Line+1,Line+n+1,Compare);24        long long Sum=0,Ans=0;25        for(int i=1;i<=n;i++){26            Ans=max(Ans,Line[i].Need-Sum);27            Sum+=Line[i].Change;28        }29        printf("%lld\n",Ans);30    }31    return 0;32}