附带整个过程的证明
推荐博客:http://t.csdn.cn/goU0n
1:记录一个偏移量
{
因为每隔特定的时间每个蚯蚓的长度都发生相同的变化,
所以每次蚯蚓成长后的长度大小不变
因此我们不需要记录每次蚯蚓的长度只需要记录其原始长度,
每次从原始长度以及被切成两段的蚯蚓中选择一个最大值即可
}
2:证明左右端最大性
{
1:建立三个队列q1, q2, q3;
{
1:q1为所有蚯蚓的原始长度;
2:q2为每次蚯蚓被切之后的左半段;
3:q3为每次蚯蚓被切之后的右半段;
}
2:将q1从大到小排列:
{
先证明一个性质:若x1 >= x2则在后面不管何时x1被切成的左右端,大于x2被切成的左右端
先证明左半段:
{
假设x1在第一秒被切则x1的左半段为[x1 * p](方括号表示下取整)
假设t秒后x2的偏移量为c则在第t秒后x2的左半段为[p * x2 + c]然后减去偏移量c
即x2的左半段长度为[p * x2 + c] - c;
所以现在只需要证明[x1 * p] >= [p * x2 + c] - c;
即[x1 * p] + c >= [p * x2 + c](这里有一个性质:若c是整数则[x1 * p] + c可以写为[x1 * p + c])
即[x1 * p + c] >= [p * x2 + c];(由于下取整具有单调性,所以下取整可以去掉)
即x1 * p + c >= p * x2 + c;
即x1 * p >= x2 * p
因为x1 >= x2所以得出结论:
若x1 >= x2则在后面不管何时x1被切成的左端,大于x2被切成的左端
}
再证明右端:
{
假设x1在第一秒被切则x1的右半段为x1 - [x1 * p](方括号表示下取整)
假设t秒后x2的偏移量为c则在第t秒后x2的右半段为x2 + c - [p * x2 + c]然后减去偏移量c
即为x2 + c - [p * x2 + c] - c;
所以现在只需要证明x1 - [x1 * p] >= x2 + c - [p * x2 + c] - c即可
将不等式整理得:x1 - [x1 * p] >= x2 - [p * x2 + c]
将不等式左边放缩:x1 - [x1 * p] >= x1 - [x1 * p + c];
所以不等式可变为:x1 - [x1 * p + c] >= x2 - [p * x2 + c](由于下取整具有单调性,所以下取整可以直接去掉)
整理后即:p <= 0
又因为0 < p < 1所以:
若x1 >= x2则在后面不管何时x1被切成的右端,大于x2被切成的右端
}
结论:只要先将q1从大到小排序那么他的左右端也是在整个左右端得序列中最大的
}
3:合并
{
由上述证明可知依次找出左端,右端,原序列中三个队列中最大的蚯蚓将他按比例切为两段
切出的左半段放入q2的队尾,右半段放入q3的队尾
为何放入队尾???
因为每次都是从大到小枚举的蚯蚓长度由上述证明可知若x1 >= x2的x1切出的的左右端大于x2切出的左右端
然后因为共有n只蚯蚓,共切了m次每切一次蚯蚓数加一所以最后有n + m只蚯蚓
}
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 7000010;//共有n只蚯蚓共切m次
typedef long long LL;
int offset;//偏移量
int q1[N], q2[M], q3[M];
int hh1, hh2, hh3, tt1, tt2 = -1, tt3 = -1;
int get_max()//找出长度最大的蚯蚓,并将其删掉
{
int x = -0x3f3f3f3f;
if (hh1 <= tt1) x = max(x, q1[hh1]);//找出长度最大的蚯蚓
if (hh2 <= tt2) x = max(x, q2[hh2]);
if (hh3 <= tt3) x = max(x, q3[hh3]);
if (hh1 <= tt1 && x == q1[hh1]) hh1 ++ ;//切完这条蚯蚓之后将这个蚯蚓删去
else if (hh2 <= tt2 && x == q2[hh2]) hh2 ++ ;
else if (hh3 <= tt3 && x == q3[hh3]) hh3 ++ ;
return x;
}
int main()
{
int n, m, q, u, v, t;
cin >> n >> m >> q >> u >> v >> t;
for (int i = 0; i < n; i ++ ) scanf("%d", &q1[i]);
tt1 = n - 1;//共读入了n个数
sort(q1, q1 + n);//先从小到大排序
reverse(q1, q1 + n);//然后翻转即为从大到小排序
for (int i = 1; i <= m; i ++ )
{
int x = get_max() + offset;
if (i % t == 0) printf("%d ", x);//每隔t秒输出最大的蚯蚓长度
int left = (LL)x * u / v, right = x - left;
offset += q;//被切的这次蚯蚓长度不增长,所以要减去第i秒生长的长度q;
left -= offset, right -= offset;
q2[++ tt2] = left, q3[++ tt3] = right;
}
puts("");
for (int i = 1; i <= m + n; i ++ )
{
int x = get_max();
if (i % t == 0) printf("%d ", x + offset);//加上偏移量
}
puts("");
return 0;
}