题解 | # P2827 [NOIP 2016 提高组] 蚯蚓 #

$[思维]$

每次将最大值 $x$ 拆成两个数 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ ，然后将除这两个数的其他所有数都加上 $q$ ，这里有是一个问题：一些数字需要加上 $q$ ，一些数字又不需要加上 $q$ ，然后多次操作下，一些数字加上 $q$ 的次数还不一样！不妨认为拆分成了 $\lfloor px \rfloor - q$ 和 $x - \lfloor px \rfloor - q$ ，这样相当于所有数字都需要加上 $q$ ，所以用一个变量 $d$ 记录所有数字一共需要加上的数。

所以可以用优先队列得到最大值，然后进行 $m$ 次操作即可：

void solve(){
    int n, m, q, u, v, t; cin >> n >> m >> q >> u >> v >> t;
    priority_queue<int> pq;  
    int d = 0;
    for(int i = 1; i <= n; i ++){
        int x; cin >> x;
        pq.push(x);
    }
    vector<int> ans;
    ans.push_back(0);
    for(int i = 1; i <= m; i ++){
        int now = pq.top();
        pq.pop();
        now += d;
        ans.push_back(now);
        int x = now * u / v - d - q, y = now - now * u / v - d - q;
        pq.push(x), pq.push(y);
        d += q;
    }
    for(int i = t; i < (int)ans.size(); i += t) cout << ans[i] << " ";
    cout << endl;
    ans.clear();
    ans.push_back(0);
    while(pq.size()){
        ans.push_back(pq.top() + d);
        pq.pop();
    }
    for(int i = t; i < (int)ans.size(); i += t) cout << ans[i] << " ";
    cout << endl;
    return ;
}

超时了3个点，因为 $m$ 的范围最大为 $7\times 10^{6}$ ，优先队列维护最大值是 $log$ 级别，所以 $m\times log(m + n)$ 约为 $10^{8}$ ，给卡超时了

所以需要将维护最大值 $log$ 级别优化，但是维护最大值不可能做到线性，还需要找到隐藏的性质：

设 $x_{1} \geq x_{2}$ ，现在取出 $x_{1}$ ，拆分的两个数 $a_{1} = \lfloor px_{1} \rfloor - q$ ， $b_{1} = x_{1} - \lfloor px_{1} \rfloor - q$

然后 $x_{2} = x_{2}+q$ ，再拆分 $x_{2}$ ，得到 $a_{2} = \lfloor p(x_{2} +q) \rfloor - q$ ， $b_{2} = x_{2} + q - \lfloor p(x_{2} + q) \rfloor - q$

然后原来的 $a_{1}$ ， $b_{1}$ 也都要加上 $q$ ，那么 $a_{1} = \lfloor px_{1} \rfloor$ ， $b_{1} = x_{1} - \lfloor px_{1} \rfloor$

现在比较 $a_{1}$ 和 $a_{2}$ 的大小， $b_{1}$ 和 $b_{2}$ 的大小

$a_{2} = \lfloor p(x_{2} +q) \rfloor - q = \lfloor px_{2} \rfloor + pq - q = \lfloor px_{2} \rfloor +q(p-1) < \lfloor px_{2} \rfloor < \lfloor px_{1} \rfloor = a_{1}$ ，故 $a_{1} > a_{2}$

$b_{2} = x_{2} + q - \lfloor p(x_{2} + q) \rfloor - q$ ，故 $b_{1} > b_{2}$

故得出结论：不仅从一开始的数组里取出的数是从大到小的，而且拆分成的两个数也是满足单调递减的。

所以我们可以建立三个普通队列，取出三个队首最大元素，然后拆分成两个元素放入第二个队列和第三个队列中.....，普通队列的操作时间复杂度为 $O(1)$ ，那么就不会超时

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


bool cmp(int a, int b){
    return a > b;
}

const int inf = -1e18;
void solve(){

    int n, m, q, u, v, t;
    cin >> n >> m >> q >> u >> v >> t;
    vector<int> a(n + 10);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n, cmp);
    int d = 0;
    queue<int> q1, q2, q3;
    for(int i = 1; i <= n; i ++) q1.push(a[i]);
    for(int i = 1; i <= m; i ++){
        int mx = inf;
        if(q1.size() && q1.front() > mx) mx = q1.front();
        if(q2.size() && q2.front() > mx) mx = q2.front();
        if(q3.size() && q3.front() > mx) mx = q3.front();
        if(q1.size() && q1.front() == mx) q1.pop();
        else if(q2.size() && q2.front() == mx) q2.pop();
        else if(q3.size() && q3.front() == mx) q3.pop(); 

        int now = mx + d;
        if(i % t == 0) cout << now << " ";
        
        int x = now * u / v, y = now - x;
        q2.push(x - d - q), q3.push(y - d - q);
        d += q;
    }
    cout << endl;
    int cnt = 0;
    while(q1.size() || q2.size() || q3.size()){
        int mx = inf;
        if(q1.size() && q1.front() > mx) mx = q1.front();
        if(q2.size() && q2.front() > mx) mx = q2.front();
        if(q3.size() && q3.front() > mx) mx = q3.front();
        if(q1.size() && q1.front() == mx) q1.pop();
        else if(q2.size() && q2.front() == mx) q2.pop();
        else if(q3.size() && q3.front() == mx) q3.pop(); 
        int now = mx + d;
        cnt ++;
        if(cnt % t == 0) cout << now << " ";
    }
    cout << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}