【题解】P7667 [JOI2018] Art Exhibition

· · 题解

题目分析

乍一看，好像有很多个变量，要在这些变量中得到答案没有那么直观。但是如果我们关注题目“令 S-(A_{\max}-A_{\min}) 最大” 这一要求，我们不难发现，当 A_{\max} 和 A_{\min} 这一范围确定之后，我们要尽可能把这一范围内的所有展品全部带走，这样才能保证 S 尽可能大，从而保证在 (A_{\max}-A_{\min}) 确定的情况下整体尽可能大。

那我们是不是应该要枚举 \max 和 \min 值呢？实际上这种思路是可行的，在 O(n\log n) 排序使得价值按序排列之后，枚举复杂度达到了 O(n^2) 级别，这样的时间复杂度还不够优秀。

所以我们考虑只枚举 \max，在确定一个 A_i 作为最小值之后，我们考虑把这个状态转移到下一个数，试图找出他们的关系。在从 A_i 转化到 A_{i+1} 之后，我们所求的目标值的变化为 B_{i-1}-(A_i-A_{i+1})，这应该是容易理解的。而实际上如果我们要连贯地将状态进行转移以方便枚举，我们就可以进行一步预处理，令：

f_i=B_i-(A_i-A_{i+1})

这样我们就可以在常数时间内实现状态的转移，鉴于复杂度瓶颈在于排序部分的 O(n\log n)，而这个复杂度已经足以通过本题，于是不继续深入考量。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct num{
    int sz,val;
    bool operator <(const num &temp)const{
        return sz<temp.sz;
    }
}a[500005];
int n,f[500005],ans,mx;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].sz>>a[i].val;
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++)
        f[i]=a[i].val-a[i+1].sz+a[i].sz;
    for(int i=1;i<=n;i++){
        int t=a[i].val;
        ans=max(ans,t+mx);
        mx=max(mx+f[i],(long long)0);
    }cout<<ans<<endl;
    return 0;
 }