CSP 201403-1 相反数

叶茂林

发布于 2023-09-13 08:21:28

1220

发布于 2023-09-13 08:21:28

文章被收录于专栏：叶子的开发者社区

答题

用两个优先队列，一个记录正数升序排序，一个记录负数降序排序，然后在两个队列都不为空的情况下取二者top相加与0比较大小，如果等于0，那么相反数的数目增加一对并同时弹出队列，如果小于0，那么弹出正数队列，如果大于0，那么弹出负数队列

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main() {
    priority_queue<int,vector<int>,greater<>> positive;
    priority_queue<int> negative;
    int n, temp, sum = 0;
    cin >> n;
    while (n--) {
        cin >> temp;
        if (temp > 0)
            positive.push(temp);
        else negative.push(temp);
    }
    while (!positive.empty() && !negative.empty()) {
        temp = positive.top() + negative.top();
        if (temp == 0) {
            positive.pop();
            negative.pop();
            sum++;
        } else if (temp < 0) {
            positive.pop();
        } else {
            negative.pop();
        }
    }
    cout << sum;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

int