蚯蚓
【问题描述】
本题中，我们将用符号
表示对c向下取整，例如：
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 n 只蚯蚓（n 为正整数）。每只蚯蚓拥有长度，我们设第 i 只蚯蚓的长度为 ai(i=1,2,…,n)，并保证所有的长度都是非负整数（即：可能存在长度为 0的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 p（是满足 0 < p < 1 的有理数）决定，设这只蚯蚓长度为 x，神刀手会将其切成两只长度分别为
的蚯蚓。特殊地，如果这两个数的其中一个等于 0则这个长度为 0 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 q（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来……（m 为非负整数）
蛐蛐国王希望知道这 m秒内的战况。具体来说，他希望知道：
m 秒内，每一秒被切断的蚯蚓被切断前的长度（有 m 个数）；
m 秒后，所有蚯蚓的长度（有 n+m 个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你……
【输入格式】
从文件earthworm.in中读入数据。
第一行包含六个整数 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 只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
【输出格式】
输出到文件earthworm.out中。
第一行输出
个整数，按时间顺序，依次输出第 t 秒，第 2t 秒，第 3t 秒，……被切断蚯蚓（在被切断前）的长度。
第二行输出
个整数，输出 m 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 t ，第 2t，第3t，……的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。
请阅读样例来更好地理解这个格式。
【样例1输入】
3 7 1 1 3 1
3 3 2
【样例1输出】
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
【样例1说明】
在神刀手到来前：3 只蚯蚓的长度为3,3,2。
1 秒后：一只长度为3 的蚯蚓被切成了两只长度分别为1 和2 的蚯蚓，其余蚯蚓的长度增加了1。最终4 只蚯蚓的长度分别为(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。
2 秒后：一只长度为4 的蚯蚓被切成了1 和3 。5 只蚯蚓的长度分别为：2,3,(1,3),4。
3秒后：一只长度为4 的蚯蚓被切断。6 只蚯蚓的长度分别为：3,4,2,4,(1,3)。
4 秒后：一只长度为4 的蚯蚓被切断。7 只蚯蚓的长度分别为：4,(1,3),3,5,2,4。
5 秒后：一只长度为5 的蚯蚓被切断。8 只蚯蚓的长度分别为：5,2,4,4,(1,4),3,5。
6 秒后：一只长度为5 的蚯蚓被切断。9 只蚯蚓的长度分别为：(1,4),3,5,5,2,5,4,6。
7 秒后：一只长度为6 的蚯蚓被切断。10 只蚯蚓的长度分别为：2,5,4,6,6,3,6,5,(2,4)。
所以，7 秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,6。7 秒后，所有蚯蚓长度从大到小排序为 6,6,6,5,5,4,4,3,2,2。
【样例2输入】
3 7 1 1 3 2
3 3 2
【样例2输出】
4 4 5
6 5 4 3 2
【样例2说明】
这个数据中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。
虽然第一行最后有一个6 没有被输出，但是第二行仍然要重新从第二个数再开始输出。
【样例3输入】
3 7 1 1 3 9
3 3 2
【样例3输出】
2
【样例3说明】
这个数据中只有t=9与上个数据不同。
注意第一行没有数要输出，但也要输出一个空行。
【子任务】
相似题推荐
如下图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是_____(2分)，最小代价的不同方案数是_______(3分)。(只要有一条删除的边不同，就是不同的方案)
如右图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0，或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要 次操作。
（最长路径）给定一个有向无环图，每条边长度为1，求图中的最长路径长度。（第五空2分，其余3分）
输入：第一行是结点数n（不超过100）和边数m，接下来m行，每行两个整数a，b，表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。
输出：最长路径长度。
提示：先进行拓扑排序，然后按照拓扑序计算最长路径。
#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100]; // 记录每个结点的入度
int len[100]; // 记录以各结点为终点的最长路径长度
int queue[100]; // 存放拓扑排序结果
int main() {
cin >> n >> m;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
graph[i][j] = 0;
for (i = 0; i < n; i++)
degree[i] = 0;
for (i = 0; i < m; i++) {
cin >> a >> b;
graph[a][b] = 1;
(1) ;
}
tail = 0;
for (i = 0; i < n; i++)
if ( (2) ) {
queue[tail] = i;
tail++;
}
head = 0;
while (tail < n - 1) {
for (i = 0; i < n; i++)
if (graph[queue[head] ][i] == 1) {
(3) ;
if (degree[i] == 0) {
queue[tail] = i;
tail++;
}
}
(4) ;
}
ans = 0;
for (i = 0; i < n; i++) {
a = queue[i];
len[a] = 1;
for (j = 0; j < n; j++)
if (graph[j][a] == 1 && len[j] + 1 > len[a])
len[a] = len[j] + 1;
if ( (5) )
ans = len[a];
}
cout << ans << endl;
return 0;
}
设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。
| A． n2 |
B． n logn |
| C． 2n |
D． 2n-1 |
