题意描述:
给你一个非负整数序列 \(A\), 其中序列元素大小为 \(a_i(a_i\leq 10^9)\).
给你 \(m(m\leq 6e7)\) 个操作, 对于每一个操作, 会选取最大的数字并将其分为两半. 分法由有理数 \(p(0<p<1)\) 决定, 将数字分为 \(\lfloor px \rfloor\) 和 \(x - \lfloor px \rfloor\) 两部分并加入序列中.
特殊地, 如果某个数变为 \(0\), 那么这个数也将得以保留.
此外, 除了刚刚产生的两个新的数字, 其余所有数字都会增加一个非负整数 \(q(q\leq 200)\).
问在每一次操作时, 集合的数字的情况.
在所有操作执行后, 集合的数字的情况.
思路:
队列.
对于假设我现在进行了一次操作, 那么假设我选出来的最大数为 \(x\) 并将其分为两份, 同时将其他数字加上 \(q\).
那么其实可以采用差分的思想将 \(\lfloor px \rfloor -q\) 和 \(x - \lfloor px \rfloor-q\) 插入原数组中, 然后再整个集合加上 \(q\), 这样做与原操作是等价的.
那么我们可以维护一个偏移量 \(delta\), 当前数字加上偏移量才是他们的真实值. 这样我们可以省去 \(O(n)\) 的对序列更新的复杂度.
似乎这样我们就可以使用优先队列来解决了, 每次取堆顶, 后将两个数插入集合, 时间复杂度 \(O(mlogm)\)(因为最后数字规模达到了 \(m+n\)). 无法通过.
设两个非负整数 \(x_1,x_2\) 且 \(x_1\geq x_2\).
对于 \(0<p<1,q<200\):
首先有 \(\lfloor px_1 \rfloor \geq\lfloor px_2 \rfloor\). ------------- 设为 \(1\) 式
再有 \(x_1-x_2\geq p(x_1-x_2)\).
即 \(x_1-px_1 \geq x_2-px_2\).
转化一下变成 \(x_1-\lfloor px_1 \rfloor \geq x_2-\lfloor px_2 \rfloor\).---------- 设为 \(2\) 式
对于 \(1\) 式和 \(2\) 式而言, 其意义在于:
\(x_1\) 转化的两个数分别不小于 \(x_2\) 转化的两个数.
换言之, 我们如果对 \(A\) 序列进行降序排序, 那么我们从 \(A\) 序列中取出的数字是单调的, 我们每次取出一个数字, 将他分为两个数字, 这两个数字也是单调的.
所以我们可以采用三个队列分别设为队列 \(1,2,3\).
将原序列降序排列后插入队列 \(1\).
分割后的数字 \(\lfloor px \rfloor\) 插入队列 \(2\).
分割后的数字 \(x-\lfloor px \rfloor\) 插入队列 \(3\).
每次取出队头相互比较, 并完成分割操作, 配合刚才差分的思路, 时间复杂度可以做到 \(O(n)\).
代码:
- #include<bits/stdc++.h>
- using namespace std;
- typedef long ll;
- const int maxn = 1e5 + 10;
- queue<ll> q1, q2, q3;
- ll n, m, q, u, v, t, a[maxn];
- bool cmp(ll a, ll b){return a> b;}
- int get_max(ll x)
- {
- ll a = -1, b = -1, c = -1;
- if(q1.size()) a = q1.front() + x * q;
- if(q2.size()) b = q2.front() + x * q;
- if(q3.size()) c = q3.front() + x * q;
- ll num = max(a, max(b, c));
- if(num == a) q1.pop();
- else if(num == b) q2.pop();
- else if(num == c) q3.pop();
- return num;
- }
- int main()
- {
- scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t);
- for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
- sort(a + 1, a + 1 + n, cmp);
- for(int i = 1; i <= n; i++) q1.push(a[i]);
- for(int i = 1; i <= m; i++)
- {
- ll x = get_max(i - 1); // 找三个队列里的最大值
- if(i % t == 0) cout << x << " ";
- ll tmp1 = x * u / v;
- ll tmp2 = x - tmp1;
- q2.push(tmp1 - i * q);
- q3.push(tmp2 - i * q);
- }
- printf("\n");
- for(int i = 1; i <= n + m; i++)
- {
- ll x = get_max(m);
- if(i % t == 0)
- cout << x << " ";
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3277467.html