25分水法：
直接模拟，增加$q$直接暴力把堆中的元素取出来加完放进去
65分水法：
直接按照题意模拟，但是堆里面存当前蚯蚓长度与 增加量$q$ 的差值(具体看代码),来避免每次使蚯蚓增加$q$.
90分水法：
发现很多数据$q=0$，那么等于蚯蚓不会再加了，考虑单调性。
用三个队列$q_1,q_2,q_3$，分别代表原始数据，切分第一部分，切分第二部分。
然后每次从三个队列里取最大值出来切，然后结果分别放进$q_2,q_3$。
这样做是对的，因为这样做数据是单调递减的，前面切的两部分一定比后面切的两部分分别大于。
然后加上65分的程序分段，这样就有90分了，注意分段程序千万别打错，不然白打前65分。
100分正解：
根据上一个90分做法，我们被暗示了——单调性。
$q≠0$也是单调的吗？是的。
我们通过反证可以知道：设$a_i$为当前被切割的蚯蚓的原长，$a_j$为$a_i$之前隔了$n$时段被切割的蚯蚓的原长
那么假设不单调，即出现：
$a_i \times p + n \times q \leq (a_j + n \times q) \times p$
那么就是
$a_i \times p + n \times q \leq a_j \times p + n \times q \times p$
因为$a_j \leq a_i, 0 < p < 1$，那么
$a_i \times p + n \times q > a_j \times p + n \times q \times p$成立
与之前的假设矛盾，因此是单调的
NOIP的部分分都是在暗示正解的方向，不过以后或者其他比赛可能回不会。所以尽可能往部分分想会暗示什么，但是也不要完全依赖部分分提示。
上述算法虽然难以证明，但是在想到90分做法以后，联想到$q≠0$，那就可以作一个假设，之后用暴力对拍即可验证正确性(你的暴力肯定要对)。
下面代码给出了3个分数档次(65,90,100)的代码：
65分堆水法：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
struct data {
LL len;
bool operator < (const data &b) const {
return len < b.len;
}
};
LL n, m, q, t, add;
db pi;
priority_queue<data> pq;
void clean() {
add = 0;
}
void solve() {
clean();
for (LL x, i = 1; i <= n; i++) scanf("%lld", &x), pq.push((data){x});
data p;
for (int i = 1; i <= m; i++) {
p = pq.top(); pq.pop();
LL len = p.len + add;
if (i % t == 0) printf("%lld ", len);
LL fir = (LL)((db)len * pi);
LL sec = len - fir;
add += q;
pq.push((data){fir - add}), pq.push((data){sec - add});
}
printf("\n");
int tot = 0;
while (!pq.empty()) {
p = pq.top(); pq.pop();
tot++;
LL len = p.len + add;
if (tot % t == 0) printf("%lld ", len);
}
printf("\n");
}
int main() {
LL u, v;
scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t), pi = (db)u / (db)v, solve();
return 0;
}
90分水法：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
struct data {
LL len;
bool operator < (const data &b) const {
return len < b.len;
}
};
LL n, m, q, t, add;
db pi;
priority_queue<data> pq;
void clean() {
add = 0;
}
void solve() {
clean();
for (LL x, i = 1; i <= n; i++) scanf("%lld", &x), pq.push((data){x});
data p;
for (int i = 1; i <= m; i++) {
p = pq.top(); pq.pop();
LL len = p.len + add;
if (i % t == 0) printf("%lld ", len);
LL fir = (LL)((db)len * pi);
LL sec = len - fir;
add += q;
pq.push((data){fir - add}), pq.push((data){sec - add});
}
printf("\n");
int tot = 0;
while (!pq.empty()) {
p = pq.top(); pq.pop();
tot++;
LL len = p.len + add;
if (tot % t == 0) printf("%lld ", len);
}
printf("\n");
}
LL q1[10000000 + 5], q2[10000000 + 5], q3[10000000 + 5];
LL h1 = 0, h2 = 0, h3 = 0, t1 = 0, t2 = 0, t3 = 0;
bool cmp(const int &a, const int &b) {
return a > b;
}
void solve2() {
for (int i = 1; i <= n; i++) scanf("%lld", &q1[i]);
sort(q1 + 1, q1 + 1 + n, cmp);
t1 = n;
for (int i = 1; i <= m; i++) {
LL maxd = -1, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
if (i % t == 0) printf("%lld ", maxd);
q2[++t2] = (LL)((db)maxd * pi);
q3[++t3] = maxd - (LL)((db)maxd * pi);
}
printf("\n");
for (int i = 1; i <= n + m; i++) {
LL maxd = -1, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
if (i % t == 0) printf("%lld ", maxd);
}
printf("\n");
}
int main() {
LL u, v;
scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t), pi = (db)u / (db)v;
if (q != 0) solve(); else solve2();
return 0;
}
100分正解：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
LL n, m, q, t, add;
db pi;
void clean() {
add = 0;
}
bool cmp(const int &a, const int &b) {
return a > b;
}
LL q1[10000000 + 5], q2[10000000 + 5], q3[10000000 + 5];
LL h1 = 0, h2 = 0, h3 = 0, t1 = 0, t2 = 0, t3 = 0;
void solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%lld", &q1[i]);
sort(q1 + 1, q1 + 1 + n, cmp);
t1 = n;
for (int i = 1; i <= m; i++) {
LL maxd = -1000000000, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
maxd += add;
if (i % t == 0) printf("%lld ", maxd);
add += q;
q2[++t2] = (LL)((db)maxd * pi) - add;
q3[++t3] = maxd - (LL)((db)maxd * pi) - add;
}
printf("\n");
for (int i = 1; i <= n + m; i++) {
LL maxd = -1000000000, wh = 0;
if (h1 < t1) if (maxd < q1[h1 + 1]) maxd = q1[h1 + 1], wh = 1;
if (h2 < t2) if (maxd < q2[h2 + 1]) maxd = q2[h2 + 1], wh = 2;
if (h3 < t3) if (maxd < q3[h3 + 1]) maxd = q3[h3 + 1], wh = 3;
if (wh == 1) h1++; if (wh == 2) h2++; if (wh == 3) h3++;
if (i % t == 0) printf("%lld ", maxd + add);
}
printf("\n");
}
int main() {
LL u, v;
scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t), pi = (db)u / (db)v, solve();
return 0;
}
