题目很长,题意如下:一开始有n个值,,有m次操作,每次操作选择一个最大的值x,将它分解成两个数,分别为,以及
,然后,经过这个操作之后,对除了这两个数以外的其他数字进行 +q 操作。最后两行输出,第一行输出,是每次操作执行之前,我们找到的那个最大的值是多少;第二行输出,是我们执行完m次操作,现在这n+m个值都各自变成了几?
由于输入的量加上操作的量很大,所以我们不能使用带有复杂度的大根堆来解决这个问题,这无疑是加大了我们这道问题的难度!
那么,这暗示着我们需要寻找其中的“线性关系”了。
我们会发现,我们取出来的值一定是排除“增量q”情况下的递减的。但,我们再想一下,同样经过T次“增量q”,如果先分解的两个,是不是后期分得的“增量q”会更多呢(因为分解成了两个,相当于每个都享受到了这样的优惠,但是没分解的,现在是两个共享同一个“增量q”),先分解的在随着时间的推移反而会越来越有优势。
所以,我们不妨维护三个队列:
队列1:原本的值,按照从大到小排序;
队列2:分解之后,值偏大的那个,那么值越大的一定就先分解了,享受“增量q”福利肯定也更早;
队列3:分解之后,值偏小的那个,作用同上。
那么,又如何维护“增量q”呢,实际上,我们只需要再多统计一个信息就可以了,就是这个值是第几轮生成的,用当前轮次减去生成的轮次,不就得到了它需要被增加多少次了呢。
- #include
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5 + 7;
- int n, m, q, t;
- ll u, v;
- ll a[maxn];
- struct node {
- ll val, id;
- node(ll a = 0, ll b = 0):val(a), id(b) {}
- friend bool operator < (node e1, node e2) {
- return e1.val - e1.id * q < e2.val - e2.id * q;
- }
- ll F(ll i) { return val + (i - id) * q; }
- };
- struct Heap {
- queue
Q[3]; - void clear() {
- for(int i = 0; i < 3; i ++) while(!Q[i].empty()) Q[i].pop();
- }
- bool empty() { return Q[0].empty() && Q[1].empty() && Q[2].empty(); }
- node Top() {
- node ans;
- int qid = -1;
- for(int i = 0; i < 3; i ++) {
- if(Q[i].empty()) continue;
- if(~qid) {
- if(Q[qid].front() < Q[i].front()) qid = i;
- }
- else qid = i;
- }
- ans = Q[qid].front();
- Q[qid].pop();
- return ans;
- }
- } que;
- int main() {
- scanf("%d%d%d%lld%lld%d", &n, &m, &q, &u, &v, &t);
- for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
- sort(a + 1, a + n + 1, greater
() ); - que.clear();
- for(int i = 1; i <= n; i ++) que.Q[0].push(node(a[i], 0));
- int tot = m / t;
- if(!tot) printf("\n");
- for(int i = 0; i < m; i ++) {
- node now = que.Top();
- if((i + 1) % t == 0) {
- tot --;
- printf("%lld%c", now.F(i), tot ? ' ' : '\n');
- }
- ll x = now.F(i) * u / v, y = now.F(i) - x;
- if(x < y) swap(x, y);
- que.Q[1].push(node(x, i + 1));
- que.Q[2].push(node(y, i + 1));
- }
- tot = (n + m) / t;
- if(!tot) printf("\n");
- for(int i = 1; i <= n + m; i ++) {
- node now = que.Top();
- if(i % t == 0) {
- tot --;
- printf("%lld%c", now.F(m), tot ? ' ' : '\n');
- }
- }
- return 0;
- }