codeforces 361 C. Levko and Array Recovery（暴力+思维）

题目链接：http://codeforces.com/contest/361/problem/C

题意：对一个数列有这么两个操作

1、(1,l,r,p)..将区间[l,r]所有数都加上p

2、(2,l,r,m).求出区间[l,r]的最大值为m

现在告诉这么一些操作(<5000个)，问能否找到一个原始的数列，有则输出YES与这个数列，否则输出NO，答案可能不唯一输出任何合法的都行。

题解：先给数组赋予最大的初值然后倒着处理，遇到1就减去。如果是2，将这一区间里所有数都去min(自身，MAX)

处理完之后然后正着来看一下是不是符合条件。由于数据比较小直接暴力也行。

#include <iostream>

#include <cstring>

#include <cstdio>

#define inf 0X3f3f3f3f

using namespace std;

typedef long long ll;

const int M = 5e3 + 10;

struct TnT {

    int t , l , r , w;

}T[M];

ll a[M] , b[M];

int main() {

    int n , m;

    scanf("%d%d" , &n , &m);

    for(int i = 0 ; i < m ; i++) {

        scanf("%d%d%d%d" , &T[i].t , &T[i].l , &T[i].r , &T[i].w);

    }

    for(int i = 1 ; i <= n ; i++) {

        a[i] = 25 * 100000000000;

    }

    int flag = 0;

    for(int i = m - 1 ; i >= 0 ; i--) {

        if(T[i].t == 1) {

            for(int j = T[i].l ; j <= T[i].r ; j++) {

                a[j] -= T[i].w;

            }

        }

        else {

            for(int j = T[i].l ; j <= T[i].r ; j++) {

                a[j] = min(a[j] , (ll)T[i].w);

            }

        }

    }

    for(int i = 1 ; i <= n ; i++) {

        b[i] = a[i];

    }

    for(int i = 0 ; i < m ; i++) {

        if(T[i].t == 1) {

            for(int j = T[i].l ; j <= T[i].r ; j++) {

                b[j] += T[i].w;

            }

        }

        else {

            int count = 0;

            for(int j = T[i].l ; j <= T[i].r ; j++) {

                if(b[j] > T[i].w) {

                    flag = 1;

                    break;

                }

                if(b[j] == T[i].w) count++;

            }

            if(!count) {

                flag = 1;

                break;

            }

        }

        if(flag) break;

    }

    if(flag) printf("NO\n");

    else {

        printf("YES\n");

        for(int i = 1 ; i <= n ; i++) {

            a[i] = min((ll)1000000000 , a[i]);

            a[i] = max((ll)-1000000000 , a[i]);

            printf("%I64d " , a[i]);

        }

        printf("\n");

    }

    return 0;

}

巴特西

codeforces 361 C. Levko and Array Recovery（暴力+思维）

最新文章

热门文章