G题的构造方法

以下讨论建立在不存在0且至少存在一个-1的基础上:

记录1和-1的出现次数分别为a, b,注意到当a >= b的时候,一定可以构造(任意>0个1可以与1个 -1消掉)

当a < b的时候,可以发现两个-1也可以变成一个1, 相当于把b的一部分借给a,因此a < b也可能有解

let x := b借给a的数量

then a + x >= b - 2x

移项得 3x >= b - a

注意:b - 2x > 0 ——> x <= (b - 1) / 2(下取整)

同时x >= 0 , 故x范围是[0, (b - 1) / 2(下取整)]

则只需要 3 * ((b - 1) / 2) >= b - a 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;


void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> nums(n);
    for(auto& num : nums){
        cin >> num;
    }

    for(int i = 0; i < q; i++){
        int x; 
        cin >> x;
        int cnt1 = count(nums.begin(), nums.end(), 1);
        int cnt0 = count(nums.begin(), nums.end(), 0);
        int cntn1 = count(nums.begin(), nums.end(), -1);
        if(cnt0 > 0 ){
            cout << "Yes\n";
            continue;
        }else if(cntn1 == 0){
            cout << "No\n";
            continue;
        }else{
            int high = (cntn1 - 1) / 2;
            if(3 * high >= cntn1 - cnt1){
                cout << "Yes\n";
            }else{
                cout << "No\n";
            }
        }
    }
}

int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

全部评论

相关推荐

06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务