hdu-6698 Coins 优先队列 dp

#include <stdio.h>
#include <algorithm>
#include <queue>

#define  _debug(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> node;
int n, q;
int kase;
node a[MAXN];
node ab[MAXN];
short used[MAXN];
int ans[MAXN << 1];

void solv(int i) {
  	//数组转优先队列。
    priority_queue<node> qa(a, a + n);		
    priority_queue<node> qab(ab, ab + n);

    for (int x, xi, y, yi, z, zi; i <= 2 * n; i += 2) {
        ans[i] = ans[i - 2];
        z = x = y = -1;
        zi = xi = yi = -1;

        while (!qa.empty() && used[qa.top().second] >= 2)qa.pop();
        if (!qa.empty() && qa.size() >= 2) {
            x = qa.top().first;
            xi = qa.top().second;
            qa.pop();

            while (!qa.empty() && used[qa.top().second] >= 2)qa.pop();
            if (!qa.empty()) {
                y = qa.top().first;
                yi = qa.top().second;
                qa.pop();
            } else {
                qa.emplace(x, xi);
                x = xi = -1;
            }
        }

        while (!qab.empty() && used[qab.top().second] > 0)qab.pop();
        if (!qab.empty()) {
            z = qab.top().first;
            zi = qab.top().second;
            qab.pop();
        }

        if (x + y > z) {
            ans[i] += x + y;
            used[xi]++;
            used[yi]++;

            if (used[xi] == 1)qa.emplace(ab[xi].first - x, xi);
            if (used[yi] == 1)qa.emplace(ab[yi].first - y, yi);
            if (z != -1)qab.emplace(z, zi);
        } else {
            ans[i] += z;
            used[zi] += 2;
            if (x != -1)qa.emplace(x, xi);
            if (y != -1)qa.emplace(y, yi);
//            if (z != -1)qa.emplace(z - a[zi].first, zi);
        }
    }
}

int main() {
    scanf("%d", &kase);
    while (kase--) {
        scanf("%d", &n);
        int maxx = 0, maxi = 0;
        for (int x, y, i = 0; i < n; i++) {
            scanf("%d%d", &x, &y);

            if (x > maxx) {
                maxx = x;
                maxi = i;
            }

            a[i] = {x, i};
            ab[i] = {x + y, i};
        }

        for (int i = 0; i < n; ++i)used[i] = 0;
        solv(2);

        for (int i = 0; i < n; ++i)used[i] = 0;
        ans[1] = maxx;
        a[maxi].first = ab[maxi].first - a[maxi].first;
        used[maxi] = 1;
        solv(3);

        for (int i = 1; i <= 2 * n; ++i)
            printf("%d%c", ans[i], " \n"[i == n + n]);

    }
    return 0;
}