MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 10763 - Foreign Exchange
AOAPC II

UVaOJ 10763 - Foreign Exchange

Chai
2021-11-24 0:00:00在线评测阅读 475

问题描述

p10763

原题链接:UVaOJ 10763 - Foreign Exchange

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-4

解法一:集合(带重复元素)

由于可能存在重复的匹配对,所以要用 multiset 来统计,在匹配到的时候记得按情况清理 key 即可:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int n, a, b;
  while (cin >> n && n) {
    map<int, multiset<int>> mem;
    while (n--) {
      cin >> a >> b;
      if (mem.find(b) != mem.end() && mem[b].find(a) != mem[b].end()) {
        mem[b].erase(mem[b].find(a));
        if (mem[b].size() == 0) mem.erase(b);
      } else {
        mem[a].insert(b);
      }
    }
    cout << (mem.size() ? "NO" : "YES") << endl;
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz