CodeForces 360A - Levko and Array Recovery （模拟）

题目地址：点击打开链接

思路：

维护每个数的上下界，先按照操作倒着求一遍，可以得到每个数的上界，再按操作正着验证一遍是否能够满足。如果都能满足的话输出上界即可。

代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 5e3+5;const int INF = 0x3f3f3f3f/10;int l[maxn], r[maxn], cmd[maxn][4], ans[maxn], n, m;int main(void){    while(cin >> n >> m)    {        for(int i = 1; i <= n; i++)            l[i] = -INF, r[i] = INF;        for(int i = 1; i<= m; i++)            for(int j = 0; j < 4; j++)                scanf("%d", &cmd[i][j]);        bool ok = 1;        for(int i = m; i >= 1; i--)        {            if(cmd[i][0] == 1)            {                for(int j = cmd[i][1]; j <= cmd[i][2]; j++)                {                    l[j] -= cmd[i][3];                    r[j] -= cmd[i][3];                }            }            else            {                int need = 0;                for(int j = cmd[i][1]; j <= cmd[i][2]; j++)                {                    if(l[j] > cmd[i][3])                    {                        ok = 0;                        break;                    }                    else                    {                        if(r[j] >= cmd[i][3]) r[j] = cmd[i][3], need = 1;                    }                }                if(!need) ok = 0;            }//            for(int i = 1; i <= n; i++)//            PRintf("%d : %d %d/n", i, l[i], r[i]);//            printf("/n");        }        if(!ok) puts("NO");        else        {            //puts("YES");            bool ok = 1;            for(int i = 1; i <= n; i++)                ans[i] = r[i];            for(int i = 1; i <= m; i++)            {                if(cmd[i][0] == 1)                {                    for(int j = cmd[i][1]; j <= cmd[i][2]; j++)                        ans[j] += cmd[i][3];                }                else                {                    int need = 0;                    for(int j = cmd[i][1]; j <= cmd[i][2]; j++)                        if(ans[j] >= cmd[i][3]) need = 1;                    if(!need) ok = 0;                }            }            if(!ok) puts("NO");            else            {                puts("YES");                for(int i = 1; i <= n;i++)                    printf("%d%c", r[i], i==n ? '/n' : ' ');            }        }    }    return 0;}