Codeforces Round #394 (Div. 2) D. Dasha and Very Difficult Problem 贪心

My Solution

题意：数组a、b，由bi - ai 得到ci，要求每个ci都不相同，给定a和p(p为c的压缩之后的保持大小顺序不变的序列)，求b。

贪心

可以令 ci = pi + k，因为p为c的压缩之后的保持大小顺序不变的序列。

然后bi = ai + ci = ai + pi + k;

然后可以求出bi，这是用maxv = max{bi}，minv = min{bi},然后如果 minv~maxv的宽度大于lr的宽度，则ans = -1；

否则，把区间minv~maxv 移到 lr里，如果偏小就每个bi都加(l - minv)，如果偏大就每个bi都减 (maxv - r)。

复杂度 O(n)

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;
const int INF = 1e9 + 8;

int a[maxn], b[maxn], p[maxn];

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, l, r, i, maxv = -INF, minv = INF;
    cin >> n >> l >> r;
    for(i = 0; i < n; i++) cin >> a[i];
    for(i = 0; i < n; i++) cin >> p[i];
    for(i = 0; i < n; i++){ b[i] = a[i] + p[i]; maxv = max(maxv, b[i]); minv = min(minv, b[i]); } if(maxv - minv + 1 > (r - l + 1)) cout << -1 << endl;
    else{
        //cout << maxv << " " << minv<<endl;
        if(minv < l){
            for(i = 0; i < n; i++){ b[i] += (l - minv); } } else if(maxv > r){
            for(i = 0; i < n; i++){
                b[i] -= (maxv - r);
            }
        }

        cout << b[0];
        for(i = 1; i < n; i++) cout << " " << b[i];

    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx