题解：CF2065C1 Skibidus and Fanum Tax (easy version)

canwen · 2025-02-11 16:36:29 · 题解

简单题，建议橙。

提供一种逆序遍历的做法。

我们从后往前看，假如 a_i\le a_{i+1}(1\le i\le n)，如果 a_i \gets b_1-a_i 能使 a_i 更大且 i=n（最后一个元素）或者 b_1-a_i\le a_{i+1}（仍能满足单调非递减的条件），那么贪心将 a_i \gets b_1-a_i；假如 a_i > a_{i+1}，如果 a_i \gets b_1-a_i 能使得 a_i \le a_{i+1}，那么更改，否则因为不满足单调非递减的条件，一定无解。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _reps(i,a,b,c) for(int i=(a);i<=(b);c)
#define _rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define _rreps(i,a,b,c) for(int i=(a);i>=(b);c)
#define _graph(i) for(int i=head[u];i;i=e[i].nxt)
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define pb push_back
#define mk make_pair
#define fst first
#define snd second
#define pc putchar('\n')
#define nowtime (double)clock()/CLOCKS_PER_SEC
int in(){int k=0,kk=1;char a=getchar();while(!isdigit(a)){if(a=='-') kk=-1;a=getchar();}while(isdigit(a))k=(k<<3)+(k<<1)+a-'0',a=getchar();return k*kk;}
void out(int a){if(a<0) putchar('-'),a=-a;if(a>9) out(a/10);putchar('0'+a%10);}
const int N = 2e5 + 5, M = 2;
int a[N],b[M];
signed main(){
    int t;
    t=in();
    while(t--){
        int n = in(), m = in(), flag = 1;
        _rep(i,1,n) a[i] = in();
        _rep(i,1,m) b[i] = in();
        _rrep(i,n,1){
            if(i!=n&&a[i]>a[i+1]){
                if(b[1]-a[i]<=a[i+1] )a[i] = b[1]-a[i];
                else {flag = 0; break;} 
            }else if(b[1]-a[i]>a[i]&&(i==n||b[1]-a[i]<=a[i+1])) a[i] = b[1]-a[i];
        }
        if(flag) printf("Yes\n");
        else printf("NO\n");
    }
    return 0;
}