2022牛客多校（六）

2022牛客多校（六）

一、比赛小结

比赛链接： "蔚来杯"2022牛客暑期多校训练营6

二、题目分析及解法（进阶题） A、Array

题目链接：A-Array

题意：

给出序列 a i a_i ai​ ，满足： ∑ i = 1 n 1 a i ≤ 1 2 \displaystyle \sum_{i=1}^n \frac1{a_i}\leq \frac12 i=1∑n​ai​1​≤21​ ，要求你构造出 c i , i = 0 , . . . , m − 1 c_i, i=0, ..., m-1 ci​,i=0,...,m−1 。使得， c i c_i ci​ 所对应的无限序列 b i b_i bi​ ，有： 任意连续的 a i a_i ai​ 个元素中，一定存在一个元素为 i i i

题解：

考虑条件倒数和小于等于 1/2 怎么用，每个 a_i 改成小于他最大的 2 的幂，显然倒数和小于等于 1，按照哈夫曼树合并即可

代码：

#include 
using namespace std;
bool Mbe;
constexpr int N = 1  n;
  for (int i = 1; i > a[i], p[i] = make_pair(1