問題概述

原題參考：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