首页 > 试题广场 >

大橘为重

[编程题]大橘为重
  • 热度指数:592 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
新买了一些橘子,每个橘子都有一个重量,但是的强迫症使得她希望这些橘子的重量之和恰好为
为此可以进行若干次“筛选”(也可以不进行)
每次”筛选“包含以下两个步骤:
1.计算现有橘子重量的平均数并且向下取整,记为
2.选择抛弃所有重量大于的橘子或者抛弃所有重量小于等于的橘子

输入描述:
第一行输入两个正整数 
第二行输入  个正整数,第  个正整数表示第  个橘子的重量a_i
接下来  行表示  次询问,每行一个正整数



输出描述:
对于每次询问,判断能否通过若干次“筛选”(可能0次),使得些橘子的重量之和恰好为
若能输出YES,否则输出NO
示例1

输入

5 3
7 2 1 6 5
3
21
30

输出

YES
YES
NO

说明

对于第一个询问,可以执行一次筛选操作:avg=4,抛弃大于avg的橘子,剩下的橘子为 2 1 恰好和为3,输出YES
对于第二个询问,可以执行零次筛选操作,和为7+2+1+6+5=21,输出YES
对于第三个询问,显然无法办到,所以输出NO

备注:
每次询问是独立的,也就是要从初始状态开始“筛选”
注意题目中的或者,直接dfs找出所有可能的s,存起来,后面直接查询即可。
对于dfs搜索数,可以发现,最差的情况是每次元素个数都删掉一半,即便是这样,深度最多为logn,总的可能(节点数)数量大概2^(logn+1),大概就是1e5,所以不会超时。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, q;
ll a[100010];
unordered_map<ll, int > mp;

void dfs(multiset<ll> se) {
    ll sum = 0;
    for(auto x: se) sum += x;
    mp[sum] = 1;

    if(se.size() == 1) return;

    ll avg = sum / (ll)se.size();
    multiset<ll> se_min, se_max;
    for(auto x: se)
        if(x > avg) se_max.insert(x);
        else se_min.insert(x);
    
    if(se_max.size() == 0 || se_min.size() == 0) return;
    dfs(se_max);
    dfs(se_min);
}

int main()
{
    scanf("%d%d", &n, &q);
    multiset<ll> se;
    for(int i = 1; i <= n; i ++) scanf("%lld", a + i), se.insert(a[i]);
    dfs(se);

    while(q --) {
        ll s; scanf("%lld", &s);
        if(mp.count(s)) puts("YES");
        else puts("NO");
    }
    return 0;
}


发表于 2022-03-05 18:07:58 回复(0)
这道题我用 前缀和 + unordered_map去重 + 二分 + 各种特殊条件判断 都过不了
好难啊
#include <iostream>
#include <fstream>
#include <algorithm>
#include <unordered_map>

using namespace std;

//最多 1e5 个橘子
const int N = 100010;

//每个橘子的重量
int ary[N];
//前缀和:sN[i]表示 从 [1,i] 号橘子的总重量
long long sN[N];

bool check(const int& s, int l, int r) {
    if (l > r || (l == r && s != sN[r] - sN[l - 1])) return false;
    if (s > sN[r] - sN[l - 1]) return false;
    if (s == sN[r] - sN[l - 1]) return true;
    //找到大于avg的分界点
    int avg = (sN[r] - sN[l - 1]) / (r - l + 1);
    int left = l, right = r;
    while (left < right) {
        int mid = left + right >> 1;
        if (ary[mid] > avg) right = mid;
        else left = mid + 1;
    }
    //决策1 抛弃所有重量大于avg的橘子
    if (check(s, l, right - 1) == true) return true;
    //决策2 抛弃所有重量小于等于avg的橘子
    return check(s, right, r);
}

int main() {
    //n:橘子数量
    //q:查询数量
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) cin >> ary[i];

    sort(ary + 1, ary + 1 + n);
    for (int i = 1; i <= n; ++i) sN[i] = sN[i - 1] + ary[i];

    unordered_map<int, bool> mem;
    while(q--) {
        int s;
        cin >> s;
        if (s > sN[n] || s < sN[1]) {
            cout << "NO\n";
            continue;
        }
        if (s == sN[n]) {
            cout << "YES\n";
            continue;
        }
        if (mem.find(s) != mem.end()) {
            mem[s] == true ? cout << "YES\n" : cout << "NO\n";
            continue;
        }

        //来到这里说明s一定小于橘子的总重量,且没被判断过
        if (check(s, 1, n) == true) {
            cout << "YES\n";
            mem[s] = true;
        }
        else {
            cout << "NO\n";
            mem[s] = false;
        }
    }

    return 0;
}


```
发表于 2022-02-18 17:18:31 回复(0)
看了各位大佬的思路后,我粗浅认为 本题不能使用sort来排序,一次次遍历都比排序消耗的时间少,我也不太懂为啥,但确实不排序就可以通过了。
一下是我参考了 楼上 五个臭皮蛋朋友的代码写出来的。
#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
set<ll> res;
void dfs(multiset<ll> oranges, ll sum){
    res.insert(sum);
    ll avg = sum/oranges.size();
    multiset<ll> set_min, set_max;
    ll small = 0;
    for(ll i:oranges){
        if(i>avg){
            set_max.insert(i);
        }else{
            set_min.insert(i);
            small += i;
        }
    }
    res.insert(small);
    res.insert(sum-small);
    if(set_min.size()==0 || set_max.size()==0){
        return;
    }
    dfs(set_min, small);
    dfs(set_max, sum-small);
}
int main(){
    int n, q; cin >> n >> q;
    multiset<ll> oranges;
    ll weight;
    ll sum = 0;
    for(int i=0;i<n;i++){
        cin>>weight;
        oranges.insert(weight);
        sum += weight;
    }// 导入所有橘子重量
    dfs(oranges, sum);
    while((q--)>0){
        cin>>weight;
        if(res.find(weight)==res.end()){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
        }
    }
    return 0;
}
发表于 2022-06-11 15:15:14 回复(0)
这题,第一个例子就太死亡了吧
发表于 2022-03-11 12:41:48 回复(0)