博客园同步
题目链接
简要题意：
n n n 个艺术品，分别有尺寸 A i A_i Ai 和价值 B i B_i Bi. 选定若干艺术品的“总价值”为 其价值之和减去尺寸的极差。极差即为最大值和最小值的差。求这个“总价值”的最大值。
n ≤ 5 × 1 0 5 n \leq 5 \times 10^5 n≤5×105， 1 ≤ A i ≤ 1 0 15 1 \leq A_i \leq 10^{15} 1≤Ai≤1015， 1 ≤ B i ≤ 1 0 9 ( 1 ≤ i ≤ n ) 1 \leq B_i \leq 10^9 (1 \leq i \leq n) 1≤Bi≤109(1≤i≤n).
首先考虑一个 O ( n 2 ) \mathcal{O}(n^2) O(n2) 的简易做法。
套路按 A A A 排序，贪心地，如果在已选定的若干艺术品中可以加入一个艺术品，使得该艺术品的尺寸在原来的最大值和最小值之间，那么该艺术品可以加入，这样是不用减去极差就可以加价值的操作。
所以按 A A A 排序后，选的艺术品必然是一个连续的区间，这样可以套路设 s s s 为 B B B 的前缀和，快速计算价值之和。
这样枚举左端点 i i i，扩展右端点 j j j，则 [ i , j ] [i,j] [i,j] 的“总价值”为：
s j − s i − 1 − ( a j − a i ) s_j - s_{i-1} - (a_j - a_i) sj−si−1−(aj−ai)
时间复杂度： O ( n 2 ) \mathcal{O}(n^2) O(n2).
考虑如何优化算法一？
套路枚举左端点 i i i，如何快速确定 j j j？
s j − s i − 1 − ( a j − a i ) = ( a i − s i − 1 ) + ( s j − a j ) s_j - s_{i-1} - (a_j - a_i) = (a_i - s_{i-1}) + (s_j - a_j) sj−si−1−(aj−ai)=(ai−si−1)+(sj−aj)
其中 a i − s i − 1 a_i - s_{i-1} ai−si−1 当我们选定 i i i 后就不变了，我们需要快速求出 max j = i n ( s j − a j ) \max_{j=i}^n (s_j - a_j) maxj=in(sj−aj).
令 tmax i = max j = i n ( s j − a j ) \text{tmax}_i = \max_{j=i}^n (s_j - a_j) tmaxi=maxj=in(sj−aj)，考虑如何预处理 tmax \text{tmax} tmax？
很显然，倒着枚举 i i i，用 tmax i + 1 \text{tmax}_{i+1} tmaxi+1 的结果和当前的 s i − a i s_i - a_i si−ai 取一个较大即可。
时间复杂度： O ( n ) \mathcal{O}(n) O(n).
注：这里有一个小细节。如果你这样写：
typedef long long ll; const int N=5e5+1; ... struct art { ll A,B; } a[N]; ... for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].B; for(int i=n;i>=1;i--) tmax[i]=max(tmax[i+1],s[i]-a[i].A);将会得到错误的答案。
观察可以发现，答案可能是负数，所以 tmax \text{tmax} tmax 也可能是负数。
而数组默认 tmax n + 1 = 0 \text{tmax}_{n+1} = 0 tmaxn+1=0，这样会影响整个数组，因而答案错误。
所以要预先处理一个极小值。
时间复杂度： O ( n ) \mathcal{O}(n) O(n).
实际得分： 100 p t s 100pts 100pts.
168 168 168 个测试点好评
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+2; inline ll read(){char ch=getchar(); ll f=1; while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();} ll x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;} struct art { ll A,B; } a[N]; int n; ll tmax[N],s[N]; ll ans=-(1ll<<62); inline ll max(ll x,ll y) {return x>y?x:y;} inline bool cmp(art x,art y) { return x.A<y.A; } int main() { n=read(); tmax[n+1]=ans; // ans 此时为极小值 for(int i=1;i<=n;i++) a[i].A=read(),a[i].B=read(); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].B; for(int i=n;i>=1;i--) tmax[i]=max(tmax[i+1],s[i]-a[i].A); for(int i=1;i<=n;i++) ans=max(ans,a[i].A-s[i-1]+tmax[i]); printf("%lld\n",ans); return 0; }