目录
问题概述
原题参考：C. Find B
对于一个数组a，给出m次咨询，问对于每一次询问的区间是否可以构建出另外一个好的数组b，对于a的好数组的定义是
- a数组和b数组的元素和相同
- a数组和b数组的每一位不同
- b数组的每一位是正数
思路分析
对于第一个条件和第二个条件，其实可以发现对于任意两个元素，一增一减即可，也就是保持增减平衡，但是由于第三个条件的要求，因此元素1是没有办法减的，只能向上加，其余的元素都是可以减的。因此对于一个区间，只需要判断其中1的个数和其余元素减到1的和的比较即可，当其余元素的和可以满足1的增需求，那么就可以构造数组，否则不可以构造数组
参考代码
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 3e5+7;
ll n, m, a[N], pre[N], one[N];
void solve() {
cin >> n >> m;
for(int i=1; i<=n; i++) {
cin >> a[i];
one[i] = (a[i] == 1 ? 1 : 0) + one[i-1];
pre[i] = pre[i-1] + a[i] - 1;
}
int lt, rt;
while(m --) {
cin >> lt >> rt;
if(lt == rt) cout << "NO" << endl;
else {
ll cntOne = one[rt] - one[lt-1], change = pre[rt] - pre[lt-1];
if(cntOne <= change) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
问题反思
还想复杂了，事实就是根据复杂的来想，走不出来emmm
标签：cfECR162,const,int,ll,long,数组,Find,define From： https://www.cnblogs.com/notalking569/p/18042236