洛谷 P2827 蚯蚓

题目描述（题目还是到链接里去看吧（点标题），这里复制的时候有点问题）

本题中，我们将用符号 $\lfloor c \rfloor⌊c⌋ 表示对 cc 向下取整，例如： \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3 。$

蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 $a_iai ( i=1,2,\dots,ni=1,2,…,n )，并保证所有的长度都是非负整数（即：可能存在长度为 00 的蚯蚓）。$

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 $\lfloor px \rfloor⌊px⌋ 和 x - \lfloor px \rfloorx−⌊px⌋ 的蚯蚓。特殊地，如果这两个数的其中一个等于 00 ，则这个长度为 00 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 qq （是一个非负整常数）。$

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要

蛐蛐国王希望知道这

蛐蛐国王当然知道怎么做啦！但是他想考考你……

输入输出格式

输入格式：

第一行包含六个整数

第二行包含 $a_1, a_2, \dots, a_na1,a2,…,an ，即初始时 nn 只蚯蚓的长度。$

同一行中相邻的两个数之间，恰好用一个空格隔开。

保证 $\leq n \leq 10^51≤n≤105 ， 0 \leq m \leq 7 \times 10^60≤m≤7×106 ， 0 < u < v \leq 10^90<u<v≤109 ， 0 \leq q \leq 2000≤q≤200 ， 1 \leq t \leq 711≤t≤71 ， 0 \leq a_i \leq 10^80≤ai≤108 。$

输出格式：

第一行输出 $\left \lfloor \frac{m}{t} \right \rfloor⌊tm⌋ 个整数，按时间顺序，依次输出第 tt 秒，第 2t2t 秒，第 3t3t 秒，……被切断蚯蚓（在被切断前）的长度。$

第二行输出 $\left \lfloor \frac{n+m}{t} \right \rfloor⌊tn+m⌋ 个整数，输出 mm 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 tt ，第 2t2t ，第 3t3t ，……的长度。$

同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。

请阅读样例来更好地理解这个格式。

输入输出样例

输入样例#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

输入样例#2：

3 7 1 1 3 2
3 3 2

输出样例#2：

4 4 5
6 5 4 3 2

输入样例#3：

3 7 1 1 3 9
3 3 2

输出样例#3：

//空行
2

说明

【样例解释1】

在神刀手到来前：

3秒后：一只长度为

【样例解释2】

这个数据中只有

虽然第一行最后有一个

【样例解释3】

这个数据中只有

注意第一行没有数要输出，但也要输出一个空行。

【数据范围】

洛谷 P2827 蚯蚓【优先队列】

题解：

一看就优先队列，每次取最大的。有个注意的地方就是会生长。如果及时更新队列复杂度很高，直接弄个 sum 标记一下生长了几次，最后直接把结果加上 sum 输出即可。

这样再小小优化一下，卡卡常能拿75~85分左右。这里还需要更加优化：
我们考虑这个：对于前面被切得蚯蚓分成的两段，无论怎么杨生长后一定比后面被切的分成两段来的长。这样就有了单调性。

我们用三个单调队列：一个是原蚯蚓的，一个是 px 的，另一个是 len-px 的（因为 px 和 len-px 放在一块并不一定是单调的，所以要分开在两个队列），每次取得时候就去三个队头的最大值就行了。

和合并果子的思想一样吧！！！

这样复杂度就 O（m）了，再卡卡常，优化优化，水过去了。。。

代码：

 1 #include<bits/stdc++.h>
 2 #define N 7000005
 3 using namespace std;
 4 int n,m,q,u,v,t;
 5 bool cmp(const int &a,const int &b)
 6 {
 7     return a>b;
 8 }
 9 priority_queue<int>ans;
10 int cut1[N],cut2[N],now[N];
11 int sum;
12 double p;
13 int h0,h1,h2;
14 int t0,t1,t2;
15 int main()
16 {
17     scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
18     p=(double)u/v; int tmp;
19     for (t0=1; t0<=n; t0++)
20       scanf("%d",&now[t0]);
21     t0--; t1=t2=0; h0=h1=h2=1;
22     sort(now+1,now+t0+1,cmp);
23     int top;
24     for (int i=1; i<=m; i++)
25     {
26         if (h0>t0) {
27             if (cut1[h1]>cut2[h2]) top=cut1[h1++];
28             else top=cut2[h2++];
29         }
30         else if (now[h0]>=cut1[h1] && now[h0]>=cut2[h2])
31           top=now[h0],h0++;
32         else if (cut1[h1]>=cut2[h2] && now[h0]<=cut1[h1])
33           top=cut1[h1],h1++;
34         else top=cut2[h2],h2++;
35         top+=sum;
36         int a1=floor(p*(double)top),a2=top-a1;
37         sum+=q;
38         a1-=sum,a2-=sum;
39         cut1[++t1]=a1,cut2[++t2]=a2;
40         if (i%t==0) printf("%d ",top);
41     }    
42     putchar('\n');
43     for (int i=h0; i<=t0; i++)
44       ans.push(now[i]);
45     for (int i=h1; i<=t1; i++)
46       ans.push(cut1[i]);
47     for (int i=h2; i<=t2; i++)
48       ans.push(cut2[i]);
49     for (int i=1; ans.size(); i++)
50     {
51         if (i%t==0) printf("%d ",ans.top()+sum);
52         ans.pop();
53     }
54     return 0;
55 }

View Code

加油加油加油！！！fighting fighting fighting!!!

秒客网

洛谷 P2827 蚯蚓【优先队列】

洛谷 P2827 蚯蚓

题目描述（题目还是到链接里去看吧（点标题），这里复制的时候有点问题）

输入输出格式

输入输出样例

说明

相关文章

洛谷 P2827 蚯蚓 【优先队列】

洛谷 P2827 蚯蚓

题目描述（题目还是到链接里去看吧（点标题），这里复制的时候有点问题）

输入输出格式

输入输出样例

说明

相关文章

洛谷 P2827 蚯蚓【优先队列】