P1014 · OFFICIAL SOLUTION

P1014 灰蕈迷境官方题解

Gioush OJ · P1014 灰蕈迷境

灰蕈迷境

【题意简述】

给定若干段幻境，每段需要当前清明值至少为 $a_i$ ，完成后清明值变为 $x-a_i+b_i$ 。可以任意排列进入顺序，求能够完成所有幻境的最小初始清明值。

【部分分】

若 $n$ 很小，可以枚举所有排列并模拟。若所有幻境都有 $a_i\le b_i$ ，完成后清明值不会减少，按照 $a_i$ 从小到大处理即可；若所有幻境都有 $a_i>b_i$ ，则需要比较相邻两段幻境交换前后的最小需求。

【正解】

把幻境分成两类。对于 $a_i\le b_i$ 的幻境，它们不会降低清明值，应当优先处理，并按 $a_i$ 从小到大排序。对于 $a_i>b_i$ 的幻境，它们会消耗清明值，若相邻两段均属于这一类，交换比较可以得到 $b_i$ 较大的幻境应当排在前面。排序后从前往后模拟：若当前清明值不足 $a_i$ ，就把初始值补上这部分差额，再执行这段幻境。

【复杂度】

排序为 $\mathcal{O}(n\log n)$ ，模拟为 $\mathcal{O}(n)$ 。答案与当前清明值需要使用 long long。

【参考代码】

1#include <cstdio>2#include <cstring>3#include <algorithm>4using namespace std;5 6struct point {7    int a,b;8}P[200010];9 10bool cmp(point x,point y) {11    if (x.a<=x.b && y.a>y.b) return true;12    if (x.a>x.b && y.a<=y.b) return false;13    else if (x.a<=x.b && y.a<=y.b) return x.a<y.a;14    else return x.b>y.b;15}16 17int main() {18    freopen("spore.in","r",stdin);19    freopen("spore.out","w",stdout);20    int n;long long Now=0,Ans=0;21    scanf("%d",&n);22    for (int i=1;i<=n;i++) {23        scanf("%d%d",&P[i].a,&P[i].b);24    }25    sort(P+1,P+n+1,cmp);26    for (int i=1;i<=n;i++) {27        if (P[i].a>Now){Ans+=(1ll*P[i].a-Now);Now=1ll*P[i].a;}28        Now-=1ll*P[i].a;Now+=1ll*P[i].b;29    }30    printf("%lld\n",Ans);31    return 0;32}