[NOIP2016]蚯蚓
Zenurik
·
·
题解
Description
本题中，我们将用符号⌊c⌋表示对c向下取整，例如：⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有n只蚯蚓（n为正整数)。每只蚯蚓拥有长度，我们设第i只蚯蚓的长度为a_i(i=1,2,...,n)，并保证所有的长度都是非负整数（即:可能存在长度为0的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定，设这只蚯蚓长度为x，神刀手会将其切成两只长度分别为⌊px⌋和x-⌊px⌋的蚯蚓。特殊地，如果这两个数的其中一个等于0，则这个长度为0的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加q(是一个非负整常数)。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要m秒才能到来......(m为非负整数）
蛐蛐国王希望知道这m秒内的战况。具体来说，他希望知道：
$\cdot m$秒后，所有蚯蚓的长（有$n+m$个数)。
蛐蛐国王当然知道怎么做啦！但是他想考考你......
### Input
第一行包含六个整数$n,m,q,u,v,t$，其中：$n,m,q$的意义见问题描述；
$u,v,t$均为正整数；你需要自己计算$p=u/v$(保证$0<u<v$)；$t$是输出参数，其含义将会在输出格式中解释。
第二行包含$n$个非负整数，为$a_1,a_2,...,a_n$，即初始时n只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
$1<=n<=10^5$，$0<m<7*10^6$，$0<u<v<10^9$，$0<=q<=200$，$1<t<71$，$0<ai<10^8$。
### Output
第一行输出$\frac{m}{t}$个整数，按时间顺序，依次输出第$t$秒，第$2t$秒，第$3t$秒……被切断蚯蚓（在被切断前）的长度。
第二行输出$\frac{n+m}{t}$个整数，输出$m$秒后蚯蚓的长度；需要按从大到小的顺序依次输出排名第$t$，第$2t$，第$3t$……的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。
请阅读样例来更好地理解这个格式。
### Sample Input
3 7 1 1 3 1
3 3 2
### Sample Output
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
### Solution
#### 解法一
题目要求多次询问最大值，很明显可以用二叉堆求解。
用一个优先队列保存每只蚯蚓，每次取最大值然后砍成两个数放回去。
至于处理每只蚯蚓$+=q$，遍历每个元素显然不现实。转变思路，设$add$表示到目前为止总共增加的长度，由于运动是相互的，除了新砍出来的两只以外所有蚯蚓增长$q$等价于将新砍出来的蚯蚓减去$q$。所以我们在每次$pop$时将拿出来的蚯蚓长度$+=add$，$push$时两条蚯蚓长度$-=add$即可。
时间复杂度$O((n+m)log_2(n+m))$，预期得分$65$，卡常优秀加上处理时输出能得$85$分。~~其实考场上暴力$85$分已经很可以了$qwq$~~
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 7e6 + 10;
int n, m, q, u, v, t, num, add, now, e1, e2;
double p;
priority_queue<int, vector<int>, less<int> > Q;
inline int read() {
int res = 0, flag = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') flag = -1;
for(; isdigit(c); c = getchar()) res = (res<<3) + (res<<1) + (c^48);
return res * flag;
}
int main() {
n = read(), m = read(), q = read(), u = read(), v = read(), t = read();
p = (double)u/v;
for(register int i = 1; i <= n; i++) {
register int k = read();
Q.push(k);
}
for(register int i = 1; i <= m; i++) {
now = Q.top() + add;
Q.pop();
e1 = floor((double)now*p), e2 = now - e1;
add += q;
e1 -= add, e2 -= add;
Q.push(e1), Q.push(e2);
if(!(i%t)) printf("%d ", now);
}
printf("\n");
for(int i = 1; !Q.empty(); i++) {
if(!(i%t)) printf("%d ", Q.top() + add);
Q.pop();
}
return 0;
}
```
#### 解法二
连二叉堆都不需要。
**引理：**
对于先砍的蚯蚓分成的两段中的任意一段，它一定比后切掉的蚯蚓长。
**证明：**
反证法。
假设存在这样一只长度为$a_i$的蚯蚓，它被砍后$T$秒钟砍的那只蚯蚓分成的两段长度最大。设这只蚯蚓$T$秒前的长度为$a_j$。则：
$\cdot pa_i+Tq≤(Tq+a_j)p
展开，得pa_i+Tq≤Tpq+pa_j。
因为当a_i被砍时一定有a_i>a_j，
所以pa_i>pa_j。
又因为0<p<1，
所以pa_i+Tq>Tpq+pa_j，与之前结论pa_i+Tq≤Tpq+pa_j矛盾，故假设不成立，原命题成立。
证毕。
于是可以考虑建立三个队列，其中now存储原始蚯蚓，cut1和cut2分别存储切割成的两只蚯蚓，根据引理，输出时每次取三个队头的最大值即可。蚯蚓长度增量处理方法同上。时间复杂度O(n+m)。
#include <bits/stdc++.h>
using namespace std;
const int INF = ~0U>>1;
const int M = 7e6 + 10;
int cut1[M],now[M],cut2[M];
int n, m, q, u, v, t, add, h, h1, h2, t0, t1, t2;
double p;
inline int read() {
int res = 0, flag = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') flag = -1;
for(; isdigit(c); c = getchar()) res = (res<<3) + (res<<1) + (c^48);
return res * flag;
}
inline bool cmp(const int &x,const int &y){
return x > y;
}
int main(){
n = read(), m = read(), q = read(), u = read(), v = read(), t = read();
p = (double)u/v;
for(t0 = 1; t0 <= n; t0++) now[t0] = read();
t0--;
t1 = t2 = 0;
h = h1 = h2 = 1;
sort(now+1, now+t0+1, cmp);
int top;
for(register int i = 1; i <= m; i++){
if(h > t0) {
if(cut1[h1] > cut2[h2]) top = cut1[h1++];
else top = cut2[h2++];
}
else if(now[h]>=cut1[h1] && now[h]>=cut2[h2]) top = now[h], h++;
else if(cut1[h1]>=cut2[h2] && now[h]<=cut1[h1]) top = cut1[h1], h1++;
else top = cut2[h2], h2++;
top += add;
int e1 = floor((double)top*p), e2 = top - e1;
add += q;
e1 -= add, e2 -= add;
cut1[++t1] = e1, cut2[++t2] = e2;
if(!(i%t)) printf("%d ", top);
}
printf("\n");
int i=1;
while(h<=t0 || h1<=t1 || h2<=t2) {
int flag, Max = -INF;
if(h <= t0 && now[h] > Max) Max = now[h], flag = 1;
if(h1 <= t1 && cut1[h1] > Max) Max = cut1[h1], flag = 2;
if(h2 <= t2 && cut2[h2] > Max) Max = cut2[h2], flag = 3;
if(flag == 1) h++;
else if(flag == 2) h1++;
else h2++;
if(!(i%t)) printf("%d ", Max + add);
i++;
}
return 0;
}