2019-2020 ICPC, Asia Jakarta Regional Contest E. Songwriter（贪心）

题目链接
大意：给你一个序列 $a$a,让你构造序列 $b$b满足以下条件

• $b_i>b_{i+1},if(a_i>a_{i+1})$bi​>bi+1​,if(ai​>ai+1​)
• bi​<bi+1​,if(ai​<ai+1​)
• $b_i=b_{i+1},if(a_i=a_{i+1})$bi​=bi+1​,if(ai​=ai+1​)
• $\mid b_i-b_{i+1}\mid \le k$∣bi​−bi+1​∣≤k

无解输出-1

且 $b$b中的元素都要 $\in [l,r]$∈[l,r]

我们可以递推求出每个元素的取值范围 $[l_i,r_i]$[li​,ri​]，如果范围超出边界就是无解了。

然后取的时候取能取的最小值即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
#define fi first
#define se second
#define pb push_back
int n,l,r,k,a[N],b[N];
vector<pair<int,int> >v;
int L[N],R[N];
int main() {
    scanf("%d%d%d%d",&n,&l,&r,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=n;i>=1;i--){
        if(i==n){
            L[i]=l;R[i]=r;
        }else{
            if(a[i]==a[i+1])L[i]=L[i+1],R[i]=R[i+1];
            else if(a[i]<a[i+1]){
                L[i]=max(L[i+1]-k,l);
                R[i]=R[i+1]-1;
            }else{
                L[i]=L[i+1]+1;
                R[i]=min(r,R[i+1]+k);
            }
        }
        if(R[i]<l||L[i]>r)return puts("-1"),0;
    }
    for(int i=1;i<=n;i++){
        if(i==1)printf("%d%c",L[i],' '),b[i]=L[i];
        else if(a[i]==a[i-1])printf("%d%c",b[i-1],(i==n?'\n':' ')),b[i]=b[i-1];
        else if(a[i]>a[i-1]){
            b[i]=max(L[i],b[i-1]+1);
            printf("%d%c",b[i],(i==n?'\n':' '));
        }else{
            b[i]=max(L[i],b[i-1]-k);
            printf("%d%c",b[i],(i==n?'\n':' '));
        }
    }
    return 0;
}

弱化版

这里没有元素范围和相邻数差的限制了，做法一样

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
#define fi first
#define se second
#define pb push_back
char a[N];
int b[N];
int L[N],R[N];
int main() {
    ios::sync_with_stdio(false);
    cin>>a+1;
    int n=strlen(a+1);
    L[n+1]=0;R[n+1]=1e9;
    for(int i=n;i>=1;i--){
        if(a[i]=='>'){
            L[i]=L[i+1]+1;
            R[i]=1e9;
        }else{
            L[i]=0;
            R[i]=R[i+1]-1;
        }
    }
    LL ans=0;
    ans+=L[1];int pre=L[1];
    for(int i=1;i<=n;i++){
        if(a[i]=='>'){
            pre=max(L[i+1],0);
            ans+=pre;
        }else {
            pre=max(L[i+1],pre+1);
            ans+=pre;
        }
 
    }
    cout<<ans<<endl;
    return 0;
}