Codeforces Round #661 (Div. 3)

A. Remove Smallest

题意：

给定一个序列，每次操作可以任选两个差的绝对值小于等于

排序后计算相邻数的差，只要有大于

AC代码：

const int N = 2e5 + 50;
int n, m;
int a[N];
 
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    rep(i, 1, n)
      sd(a[i]);
    sort(a + 1, a + 1 + n);
    bool flag = 1;
    rep(i, 1, n - 1)
    {
      if (a[i] == a[i + 1] || a[i] == a[i + 1] - 1)
        continue;
      else
      {
        flag = 0;
        break;
      }
    }
    if (flag)
      puts("YES");
    else
      puts("NO");
  }
  return 0;
}

B. Gifts Fixing

题意：

有 份礼物盒，礼物盒中又分了 类和 类的数量，为了公平，让 份礼物盒中 类的数量相同，

分别找到 类和 类中的最小值，只要判断当前 和

AC代码：

const int N = 2e5 + 50;
int n, m;
int a[N], b[N];
 
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    int mina = inf;
    int minb = inf;
    sd(n);
    rep(i, 1, n)
    {
      sd(a[i]);
      mina = min(a[i], mina);
    }
    rep(i, 1, n)
    {
      sd(b[i]);
      minb = min(b[i], minb);
    }
    ll ans = 0;
    rep(i, 1, n)
      ans += max(a[i] - mina, b[i] - minb);
    pld(ans);
  }
  return 0;
}

C. Boats Competition

题意：

给定一个数字序列

记录每个重量出现的次数，枚举每个二元组的和，对于每个和，看看可以组成多少二元组，然后找最大值。

AC代码：

const int N = 2e5 + 50;
int n, m;
int a[N], b[N];
 
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    mem(b, 0);
    rep(i, 1, n)
    {
      sd(a[i]);
      b[a[i]]++;
    }
    int ans = 0;
    rep(i, 1, 2 * n)
    {
      int res = 0;
      rep(j, 1, i - 1)
        res += min(b[j], b[i - j]);
      ans = max(ans, res / 2);
    }
    pd(ans);
  }
  return 0;
}

D. Binary String To Subsequences

题意：

给你一个长度为 的 串，要你把他分成若干个子序列，使得每个子序列都满足 和 交替出现，即没有相邻的 和相邻的 ，要你求最少能分成多少个子序列，以及每个元素分别分给哪一个子序列

用队列分别记录 和

AC代码：

const int N = 2e5 + 50;
int n, m;
int a[N], b[N];
char s[N];
int ans[N];
int main()
{
  int t;
  sd(t);
  while (t--)
  {
    sd(n);
    ss(s + 1);
    int cnt = 0;
    queue<int> q[2];
    rep(i, 1, n)
    {
      int now = s[i] - '0';
      if (q[now ^ 1].size())
      {
        int tmp = q[now ^ 1].front();
        q[now ^ 1].pop();
        ans[i] = tmp, q[now].push(tmp);
      }
      else
      {
        ans[i] = ++cnt;
        q[now].push(cnt);
      }
    }
    pd(cnt);
    rep(i, 1, n)
      printf("%d%c", ans[i], i == n ? '\n' : ' ');
  }
  return 0;
}