站外题 WA 求调（紧急）！！！

🎁 题目描述：庆生会 (Birthday Party)

题目描述 (Problem Description)

你正在为一位名叫 Wu_Mr 的朋友挑选生日礼物。礼物种类与数量：共有

n

种不同的礼物，每种礼物都有两份可供购买。购买价格：对于第

i

种礼物：购买第一份的花费是

a_i

。购买第二份的花费使得两份礼物的总花费为

b_i

。(这意味着购买第二份的额外花费是

b_i - a_i

)。

目标：你想要购买总共

m

份礼物。你需要找到一个购买方案，使得你的总花费最小。

输入格式 (Input Format)

输入文件名为 birthday.in。

第一行：两个整数

n

和

m

，分别表示礼物的种类数和所需购买的礼物总份数。接下来的

n

行：每行包含两个整数

a_i

和

b_i

，分别表示第

i

种礼物的第一份花费

a_i

和两份的总花费

b_i

。

示例输入 (Input 1):

6 8

66 113

81 90

69 107

18 19

50 57

2 146

📤 输出格式 (Output Format)

输出文件名为 birthday.out。

输出：仅一个整数，表示购买

m

份礼物所需的最小总花费。

示例输出 (Output 1):

234

数据范围 (Constraints)

n \le 3 \times 10^5

0 \le a_i \le 10^9

0 \le b_i \le 10^9

m \le 2n

注意：

b_i

可能小于

a_i

WA 代码（样例输出 286）：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300010;
const ll INF = 1e18;
ll a[N], b[N];
int tag[N], n, m;
int main() {
    freopen("birthday.in", "r", stdin);
    freopen("birthday.out", "w", stdout);
    ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q1, q2, q3;
    priority_queue<pair<ll, int>> q4;
    for (int i = 1; i <= n; ++i) {
        q1.emplace(a[i], i);
        q3.emplace(b[i], i);
    }
    ll ans = 0;
    for (int k = 0; k < m; ++k) {
        while (!q1.empty() && tag[q1.top().second]) q1.pop();
        while (!q2.empty() && tag[q2.top().second] != 1) q2.pop();
        while (!q3.empty() && tag[q3.top().second]) q3.pop();
        while (!q4.empty() && !tag[q4.top().second]) q4.pop();
        ll o1 = INF, o2 = INF, o3 = INF;
        int i1 = -1, i2 = -1, i3n = -1, i3o = -1;
        if (!q1.empty()) { o1 = q1.top().first; i1 = q1.top().second; }
        if (!q2.empty()) { o2 = q2.top().first; i2 = q2.top().second; }
        if (!q3.empty() && !q4.empty()) {
            o3 = q3.top().first - q4.top().first;
            i3n = q3.top().second;
            i3o = q4.top().second;
        }
        if (o1 <= o2 && o1 <= o3) {
            ans += o1;
            tag[i1] = 1;
            q4.emplace(o1, i1);
            q2.emplace(b[i1] - a[i1], i1);
        } else if (o2 <= o3) {
            ans += o2;
            tag[i2] = 2;
            q4.emplace(o2, i2);
        } else {
            ans += o3;
            if(tag[i3o]==2)
                q4.emplace(a[i3o], i3o);
            tag[i3o]--;
            tag[i3n] = 2;
            q4.emplace(b[i3n] - a[i3n], i3n);
        }
    }
    cout << ans << '\n';
    return 0;
}

站外题 WA 求调（紧急）！！！

讨论操作

回复

相关推荐

站外题 WA 求调（紧急）！！！