本题中，我们将用符号 c⌊c⌋ 表示对 cc 向下取整，例如： 3.03.13.93⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3 。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 nn 只蚯蚓（ nn 为正整数）。每只蚯蚓拥有长度，我们设第 ii 只蚯蚓的长度为 aiai ( i12ni=1,2,…,n )，并保证所有的长度都是非负整数（即：可能存在长度为 00 的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 pp （是满足 0p10<p<1 的有理数）决定，设这只蚯蚓长度为 xx ，神刀手会将其切成两只长度分别为 px⌊px⌋ 和 xpxx−⌊px⌋ 的蚯蚓。特殊地，如果这两个数的其中一个等于 00 ，则这个长度为 00 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 qq （是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 mm 秒才能到来……（ mm 为非负整数）
蛐蛐国王希望知道这 mm 秒内的战况。具体来说，他希望知道：
- mm 秒内，每一秒被切断的蚯蚓被切断前的长度（有 mm 个数）；
- mm 秒后，所有蚯蚓的长度（有 nmn+m 个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你……
输入输出格式
输入格式：
第一行包含六个整数 nmquvtn,m,q,u,v,t ，其中： nmqn,m,q 的意义见【问题描述】； uvtu,v,t 均为正整数；你需要自己计算 pu/vp=u/v （保证 0uv0<u<v ）； tt 是输出参数，其含义将会在【输出格式】中解释。
第二行包含 nn 个非负整数，为 a1a2ana1,a2,…,an ，即初始时 nn 只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
保证 1n1051≤n≤105 ， 0m71060≤m≤7×106 ， 0uv1090<u<v≤109 ， 0q2000≤q≤200 ， 1t711≤t≤71 ， 0ai1080≤ai≤108 。
这道题我看到第一反应是优先队列,但是网上说只能过80分，肖大佬只过了65分。
其实就是开三个队列，一个是原本的那些数按大小排序，一个是px，一个是x - px。每次取三个队首最大来分配，计数器记录在特定时候输出即可。
其中第一个可以用单调队列，后两个如果也用单调队列没有意义，而且会TLE4个点，期望得分80。
代码如下：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long ll; 7 ll read() 8 { 9 ll a = 0,b = 1; 10 char c = getchar(); 11 while(c < '0' or c > '9') 12 { 13 if(c == '-') b = -1; 14 c = getchar(); 15 } 16 while( c >= '0' and c <= '9') 17 { 18 a = a*10 + c -'0'; 19 c = getchar(); 20 } 21 return a * b; 22 } 23 ll maxn (ll a, ll b, ll c) 24 { 25 ll t = max(a,b); 26 return max(t, c); 27 } 28 ll n,m,q,u,v,t,a,dq = 0,cnt = 1,t1,t2,t3; 29 int main() 30 { 31 priority_queue k[2]; 32 queue k1[4]; 33 n = read(); m = read(); q = read();u = read(); v = read(); t = read(); 34 for(int i=1; i<=n; i++) 35 { 36 a = read(); 37 k[1].push(a); 38 } 39 while(cnt <= m) 40 { 41 if(cnt == 1) 42 { 43 t1 = k[1].top(); 44 t2 = k[1].top(); 45 t3 = k[1].top(); 46 } 47 else 48 { 49 t1 = !k[1].empty() ? k[1].top() : -1000000000; 50 t2 = !k1[2].empty() ? k1[2].front() : -1000000000; 51 t3 = !k1[3].empty() ? k1[3].front() : -1000000000; 52 } 53 // printf("%lld %lld %lld\n", t1, t2, t3); 54 if(cnt % t == 0) 55 printf("%lld ",maxn(t1,t2,t3) + dq); 56 if(t1 == maxn(t1,t2,t3)) 57 { 58 t1 = t1 + dq; 59 k1[2].push(t1*u/v - q - dq); 60 k1[3].push(t1 - (t1 * u / v) -dq - q); 61 k[1].pop(); 62 } 63 else 64 { 65 if(t2 == maxn(t1,t2,t3)) 66 { 67 t2 = t2+dq; 68 k1[2].pop(); 69 k1[2].push(t2*u/v - q - dq); 70 k1[3].push(t2 - (t2 * u / v) - q - dq); 71 } 72 else 73 { 74 k1[3].pop(); 75 t3+=dq; 76 k1[2].push(t3*u/v-dq-q); 77 k1[3].push(t3 - (t3 * u / v)- dq - q); 78 } 79 } 80 dq+=q; 81 cnt++; 82 } 83 printf("\n"); 84 ll tm = 1; 85 while(tm <= m + n) 86 { 87 t1 = !k[1].empty() ? k[1].top() : -1000000000; 88 t2 = !k1[2].empty() ? k1[2].front() : -1000000000; 89 t3 = !k1[3].empty() ? k1[3].front() : -1000000000; 90 if(t1 == maxn(t1,t2,t3)) 91 { 92 if(tm % t == 0) 93 printf("%lld ",t1 + dq); 94 k[1].pop(); 95 } 96 else 97 { 98 if(t2 == maxn(t1,t2,t3)) 99 {100 if(tm%t == 0)101 printf("%lld ",t2 + dq);102 k1[2].pop();103 }104 else105 {106 if(tm%t == 0)107 printf("%lld ",t3 + dq);108 k1[3].pop();109 }110 }111 tm++;112 }113 return 0;114 }