题解：P13507 [OOI 2024] Three Arrays

· · 题解

P13507 [OOI 2024] Three Arrays 题解

子任务 3，5：

作者太菜了所以最开始只会 d_i = 0 的解法。
注意到如果 d_i=0 就相当于操作的第一步不执行，所以问题就转化为第 i 次将 a 赋值为 \min(a,l_i) 或者是将 b 赋值为 \min(b,r_i)。
那么只需要枚举 a_n 的值就可以做了。将 n 个二元组 (l_i,r_i) 按照 l 排序，假如说 a_n 的值为 l_i，则 b_n 的值一定就是 \min(r_j,b_0) [1\le j <i]。每一次维护 a_n+b_n 的值，就做完了。

代码：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mpi make_pair
#define fi first
#define se second
#define lb(x) (x&-x)
using namespace std;
const double eps=1e-4;
const int maxn=1e5+10;
const int maxm=5e5+10;
const int mod=1e9+7;
const int INF=1e18;
int n,d[maxn],l[maxn],r[maxn],a0,b0,ans;
pii p[maxn];
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i=1;i<=n;i++) cin >> d[i];
    for (int i=1;i<=n;i++) cin >> l[i];
    for (int i=1;i<=n;i++) cin >> r[i];
    cin >> a0 >> b0;
    for (int i=1;i<=n;i++) p[i]=mpi(l[i],r[i]);
    sort(p+1,p+n+1);
    int b=b0;
    for (int i=1;i<=n;i++) ans=max(ans,min(p[i].fi,a0)+b),b=min(b,p[i].se);
    ans=max(ans,b+a0);
    cout << ans;
    return 0;
}

正解：

发现 d_i 每次都很难维护，考虑强行去掉 d_i。
容易发现如果在第 i 次时将 l_j 和 r_j 同时减去 d_i [i \le j]，我们并不需要将 a_i 加上 d_i，因为每个数的值都减去了 d_i，而我们只需在最后统计答案时加上 2d_i 就可以了！正解呼之欲出：预处理 d 数组的前缀和数组 s，并且将 l_i 和 r_i 减去 s_i，采用子任务 3，5 的做法并且最后将答案加上 2s_n 就得到了正解。

代码：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mpi make_pair
#define fi first
#define se second
#define lb(x) (x&-x)
using namespace std;
const double eps=1e-4;
const int maxn=3e5+10;
const int maxm=5e5+10;
const int mod=1e9+7;
const int INF=1e18;
int n,d[maxn],l[maxn],r[maxn],a0,b0,ans=-INF;
pii p[maxn];
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i=1;i<=n;i++) cin >> d[i],d[i]+=d[i-1];
    for (int i=1;i<=n;i++) cin >> l[i],l[i]-=d[i];
    for (int i=1;i<=n;i++) cin >> r[i],r[i]-=d[i];
    cin >> a0 >> b0;
    for (int i=1;i<=n;i++) p[i]=mpi(l[i],r[i]);
    sort(p+1,p+n+1);
    int b=b0;
    for (int i=1;i<=n;i++) ans=max(ans,min(a0,p[i].fi)+b),b=min(b,p[i].se);
    ans=max(ans,a0+b);
    cout << ans+d[n]*2 << "\n";
    return 0;
}