[原创]Codeforces Round #424 Div. 2 【ABCDEF】[补完]

2017-07-14 23:27:34 Tabris_ 阅读数：296

博客爬取于2020-06-14 22:39:41
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75138225

好吧、我也只能做个嘴炮选手了，，，

A Unimodal Array

——————————————————————————————————————
日常傻逼题，注意明确题意在写、

B Keyboard Layouts

——————————————————————————————————————
有一个加密方式，把26字母分别映射成一个字母，然后给你密文，让你输出原文

映射一下就好了。注意1~0和大写的情况。、

C Jury Marks

——————————————————————————————————————
给你n个评委打分的情况，和其中k次分数，问你初始分数的可能数

首先处理出打分的前缀和，能知道到第i个人评分后距离初试分数的差值
然后排序。从小到小枚举不同的差值。

然后从小到大枚举可能分数，做一个类似双指针的东西，找分数相匹配的个数比n大则有一个初始分数的可能性

D Office Keys

——————————————————————————————————————
有n个人，m个keys，目的地p，
每个人要拿一个keys到达p，
没走1m花费1个单位时间，
问所有人到达p的最小时间

首先考虑这是在直线上，从最左边的人开始枚举，那么为了方便其他人，他所拿的keys一定是尽可能靠左的

所以二分答案 check就行了

E Cards Sorting

——————————————————————————————————————
有n张卡片，成一个队列，每次操作如果队头是队列中最小的就拿出去，否则放到队尾。
问等队列为空操作了多少次

其实就是个模拟。

但是直接模拟复杂度是 $O(n^2)$ 的显然不可取

然后考虑如何维护。

首先由于有删除点，首先想到SPLAY维护，将该删除的删除，或者放到意义上的最后。
每次找当前意义上对头后面的最近的最小值

复杂度大概是 $O(n\log n\log n)$ 而且实现起来有一定难度，

然后想每一次删除相当于存在，或者不存在，想到用BIT维护即可求意义上的两次删点的操作次数。

找最小值，看到1e6的范围想到桶排，然后同样大小的要记录位置，所以开vector数组即可

维护一个意义上队头，然后二分找那个位置最近。不断维护即可

复杂度是 $O(n\log n)$

F Bamboo Partition

——————————————————————————————————————
有n个植物，最开始均为0米。每天长1米。可以认为修剪，且修建后植物不生长，。
每隔d天需要人去修剪照看。
问你在剪下去的长度和小于k的情况下 d最大为多少

最先有$ \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{n}$ 如果大于 $max\{a[x] \Big|x\in[1,n]\}$ 那么就是d的一种可能性

其实就是求 $\Big[\displaystyle \sum_{i=1}^{n} \{d\times \lceil \frac{a_i}{d} \rceil- {a_i} \} <=k \Big]$ 其中d的最大值

先排序

考虑暴力的情况，枚举答案是1~a[n] ,然后判定，

然后想二分，但是发现不满足单调性，所以不行。

考虑如何优化这个枚举过程。

首先考虑这个式子

$\displaystyle \sum_{i=1}^{n} \{d\times \lceil \frac{a_i}{d} \rceil- {a_i} \} <=k \\ \displaystyle \sum_{i=1}^{n} d\times \lceil \frac{a_i}{d} \rceil-\displaystyle \sum_{i=1}^{n} {a_i} <=k \\ \displaystyle d\times \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil<=k+\displaystyle \sum_{i=1}^{n} {a_i} \\ d<= \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{\displaystyle \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil} \\$

然后考虑分段枚举d的时候对于 $\frac{a_i}{d}$ 只有 $sqrt{}$ 种情况, 不知道的话可以先做做这道题<–戳这里

于是枚举 $d$ 即可,考虑 $d<= \dfrac{k+\displaystyle\sum_{i=1}^{0}a_i}{\displaystyle \sum_{i=1}^{n} \lceil \frac{a_i}{d} \rceil} \\$ 这个限制的同时不断维护最大值

注意d对每个a[i] 分段枚举的时候要满足所有的a[i] ,所以要取最小的.

复杂度 $O(n\times \sqrt{max\{a[x] \Big|x\in[1,n]\} })$