K. Road Widening

\(考虑每个区域可行的区间\)

\(x[1]=s[1]\ \ y[1]=s[1]+g[1]\)

\(x[i]=max(x[i-1]-1,s[i]),y[i]=min(y[i-1]+1,s[i]+g[i])\)

\(然后这样能确保每一个区间都满足前面的区间，但不意味前面的区间满足后面的区间\)

\(倒过来也做一次,之后对每个都取y[i]\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000005;
ll x[maxn],y[maxn],s[maxn],g[maxn],flag=1;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)    cin>>s[i]>>g[i];
    x[1]=s[1],y[1]=s[1]+g[1];
    for(int i=2;i<=n;i++)
    {
        x[i]=max(x[i-1]-1,s[i]);
        y[i]=min(y[i-1]+1,s[i]+g[i]);
        if(x[i]>y[i])    flag=0;
    }
    for(int i=n-1;i>=1;i--)
    {
        x[i]=max(x[i+1]-1,x[i]);
        y[i]=min(y[i+1]+1,y[i]);
        if(x[i]>y[i])    flag=0;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)    ans+=y[i]-s[i];
    if(flag==0) cout<<-1;
    else
    {
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)    cout<<y[i]<<" ";
    }
}