小新买了一些橘子,每个橘子都有一个重量,但是小的强迫症使得她希望这些橘子的重量之和恰好为。
为此小可以进行若干次“筛选”(也可以不进行)
每次”筛选“包含以下两个步骤:
1.计算现有橘子重量的平均数并且向下取整,记为
2.选择抛弃所有重量大于的橘子或者抛弃所有重量小于等于的橘子
第一行输入两个正整数第二行输入 个正整数,第 个正整数表示第 个橘子的重量接下来 行表示 次询问,每行一个正整数。
对于每次询问,判断能否通过若干次“筛选”(可能0次),使得些橘子的重量之和恰好为。若能输出YES,否则输出NO
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
每次询问是独立的,也就是要从初始状态开始“筛选”
#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; }
#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; }