526互联

Codeforces Round 689 (Div. 2, based on Zed Code Competition)D.Divide and Summarize

发布时间 2023-04-22 23:30:29作者: 蝴蝶眨几次眼睛丶

题意：

我们给定包含n个正整数的数组，我们可以对这个数组执行一些操作之后，可以让数组内元素的和成为我们想要的数。

我们对数组的执行操作一共分为三个步骤，第一个步骤是我们首先计算出数组的中间值mid。这里mid的定义不是中位数也不是均值，而是最大值和最小值的均值。也就是mid = (min + max) / 2。

得出了mid之后，我们根据数组当中元素的大小将数组分成两个部分。将小于等于mid的元素分为第一个部分，将大于mid的元素分为第二个部分。这样相当于我们把原来的大数组转化成了两个不同的小数组。

现在我们一共有q个请求，每个请求包含一个整数k。我们希望程序给出我们能否通过上述的操作使得最终得到的数组内的元素和等于k。

如果可以输出Yes，否则输出No。

题解：

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define LL long long
#define ph push_back
#define INF 0x3f3f3f3f
#define PII pair<int, int>
const int N = 1e5 + 10;
int t;
int n, q, k;
int a[N];
LL b[N];
set<LL> s;
int binary_serch(int l, int r, int val)
{

  while (l + 1 != r)
  {
    int mid = (l + r) >> 1;
    if (a[mid] <= val)
      l = mid;
    else
      r = mid;
  }
  return l;
} //二分找到左数组的右端点
void pre_query(int l, int r)
{
  if (l > r)
    return;
  if (l == r)
  {
    s.insert(a[l]);
    return;
  }                          //如果数组长度为1这点一定能查到，插入set
  s.insert(b[r] - b[l - 1]); //插入该数组的和
  int val = (a[r] + a[l]) / 2;
  int md = binary_serch(l - 1, r + 1, val);
  if (md == r)
    return;
  pre_query(l, md);
  pre_query(md + 1, r);
} //离线查询，把所有能查到的值k借助set存储
void solve()
{
  s.clear();
  memset(b, 0, sizeof b);
  cin >> n >> q;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++)
  {
    b[i] = a[i] + b[i - 1];
  } //构造前缀和方便求解数组总和
  pre_query(1, n);
  for (int i = 1; i <= q; i++)
  {
    cin >> k;
    if (s.find(k) != s.end())
      puts("Yes"); //这里set的find函数返回是迭代器，！=end（）说明找到了，奇怪的用法
    else
      puts("No");
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> t;
  // t=1;
  while (t--)
  {
    solve();
  }
  return 0;
}