Skibidus and Fanum Tax (easy version)
CodeForces – 2065C1
题目源地址
没写出来：
我刚开始想了一下用什么方法，最后还是觉得是模拟题，我是直接两两进行维护的，没有考虑到全局，还是贪心错了，我后面还想是不是方法错了，我想会不会是dfs,但是数据又太大了，肯定超时，而且对于我来说这道题的dfs我不是很会写，我还觉得dp也有可能，其实就是当前的数是否要进行操作，而且他还能进行全局的维护，这个我也觉得不太好写，开一维dp很难判断,写不出来
题目核心：贪心
因为是要非递减序列，从左到右遍历进行维护，这个简单版本是
m
=
1
m=1
m=1的，也就是每个都可以变成
x
−
a
[
i
]
x-a[i]
x−a[i],左边一定要给右边留好，左边要尽可能的小，如果序列只有一个数就不需要维护了，有多个就要开始维护了，第一个选最小的就行，接下来每个数也是从
a
[
i
]
a[i]
a[i]和
x
−
a
[
i
]
x-a[i]
x−a[i]中选，但还是要满足
a
[
i
]
<
=
a
[
i
−
1
]
a[i]<=a[i-1]
a[i]<=a[i−1]这个条件，那就把可能存
v
e
c
t
o
r
vector
vector里面，如果是空的，那么就都不满足条件，输出no,有的话就选最小的那个，然后更新
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
int b[200005];
signed main() {
int t;
cin>>t;
while(t—) {
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
for(int j=1; j<=m; j++) {
cin>>b[j];
}
int x=b[1];
int f=0;
if(n==1) {
cout<<"YES"<<endl;
continue;
} else {
int qian=min(a[1],x–a[1]);
for(int i=2; i<=n; i++) {
vector<int>v;
if(a[i]>=qian)v.push_back(a[i]);
if(x–a[i]>=qian)v.push_back(x–a[i]);
if(v.empty()) {
f=1;
break;
}
int minn=v[0];
for(int j=0; j<v.size(); j++) {
if(v[j]<minn) {
minn=v[j];
}
}
qian=minn;
}
}
if(f==1) {
cout<<"NO"<<endl;
} else {
cout<<"YES"<<endl;
}
}
return 0;
}
