寒假算法基础集训营5 E题题解

存在两种情况1.当 pre[j] ≥ pre[i] 时：S(i, j) = pre[j] - pre[i] 2.当 pre[j] < pre[i] 时：S(i, j) = pre[j] - pre[i] + p。为了最大化 S(i, j)，我们需要：1.最小化 pre[i]（针对第一种情况） 2.找到比 pre[j] 大的最小 pre[i]（针对第二种情况）

附本人ac码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 998244353
#define PLL pair<ll,ll>
const ll N=1e6+10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n,p;
	cin>>n>>p;
    vector<int>a(n);
    for(int i=0;i<n;i++) 
	{
        cin>>a[i];
    }
    vector<ll>pre(n+1,0);
    for(int i=1;i<=n;i++) 
	{
        pre[i]=(pre[i-1]+a[i-1])%p;
    }
    set<PLL>st;
    st.insert({0,0});
    ll m=-1;
    int l=0,r=0;
	for (int j=1;j<=n;j++)
	{
        ll x=pre[j];
        if(!st.empty())// 情况1：与最小的前缀和比较
		{
			PLL it=*st.begin();
            ll y=(x-it.first+p)%p;
            if(y>m) 
			{
                m=y;
                l=it.second;
                r=j-1;
            }
        }
        auto i=st.upper_bound({x, 1e18});
        if (i!=st.end())// 情况2：与大于y的最小前缀和比较
		{
			PLL it=*i;
            ll y=(x-it.first+p)%p;
            if(y>m)
			{
                m=y;
                l=it.second;
                r=j-1;
            }
        }
        st.insert({x,j});
    }
    cout<<l<<" "<<r<<" "<<m<<endl;
    return 0;
}