CF1923C
首先如果想着先满足第一个条件,使得b数组和a数组的和相同,再想着去凑第二个条件,会发现比较困难。那么不妨反过来,先尝试满足第二个条件。一个很简单的想法是,对于 \(\forall 1\le i\le m\), 如果 \(a_i = 1\),那么令 \(b_i=2\) ,否则\(b_i=1\) 。这样,再考虑去满足第一个条件。此时的b数组是满足第二、三个条件的和最小的数组。那么如果此时 \(\sum b_i > \sum a_i\) ,则第一个条件永远无法满足,直接输出 No
即可。要是 \(\sum b_i = \sum a_i\) ,此时就已经构造出了满足第一个条件的b数组,输出 Yes
。否则,计算 \(\sum a_i - \sum b_i\) ,加到一个 \(b_i\) 上即可构造出满足第一个条件的b数组啦。这个是很好证明的。只要有一个 \(b_i = 2\),那么对应的 \(a_i=1\) ,加上去 \(b_i \ne a_i\) 。如果 \(\forall 1 \le i \le m\),\(b_i = 1\),那么随便加到一个 \(b_i\) 上,很容易发现 \(b_i > a_i\)。输出 Yes
就好啦。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 300010
#define int long long
int n, q;
void solve(){
cin >> n >> q;
vector<int> a(n+1), s(n+1), p(n+1);
for(int i = 1; i <= n; i ++){
cin >> a[i];
p[i] = p[i - 1] + (a[i] == 1 ? 1 : 0); //前缀和记录a中等于1的数有多少
s[i] = s[i - 1] + a[i];
}
while(q--){
int l, r;
cin >> l >> r;
if(l == r) {cout << "No" << endl;continue;}
int ts = (p[r] - p[l - 1]) * 2 + (r - l + 1 - p[r] + p[l - 1]); //计算满足第二、三个条件的b数组的和
if(ts > s[r] - s[l - 1]){
cout << "No" << endl;
}
else cout << "Yes" << endl;
}
}
signed main(){
// freopen("shuju.in", "r", stdin);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int TN;
cin >> TN;
while(TN--){
solve();
}
return 0;
}
标签:CF1923C,le,int,sum,满足,数组,条件,Find
From: https://www.cnblogs.com/yduck/p/18031035