本文主要是介绍Codeforces #29 C. Mail Stamps,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目就是给你n个a b,让你输出所有a、b连成的线
例如:
3 3 1 100 2 3 2对应:1 3 2 100
我之前的想法是设置两个结构体,对其中一个的a元素排序,对另一个的b元素排序
再通过这两个字符串的顺序构造线,但这种思路是错的,证明就不证了。。。因为错的很明显
自己写不出来,看的别人的代码,对理解map、set的用法有很大帮助
代码如下:
#include <map>
#include <set>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define esp 1e-9
#define MAXN 10010
#define ll long long
#define INF 0x7FFFFFFF
#define BUG system("pause")
#define SW(a,b) a^=b;b^=a;a^=b;
using namespace std;
set<int> q;
map<int, int> ma;
map<int, int> mb;
void cop(int a, int b){if(ma[a])mb[a] = b;else ma[a] = b;
}void insert(int a){if(q.find(a) != q.end())q.erase(a);else q.insert(a);
}int main(void){int n;while(scanf("%d", &n)!=EOF){ma.clear();mb.clear();q.clear();int a, b;for(int i=0; i<n; ++i){scanf("%d%d", &a, &b);cop(a, b);//构造相关的ma、mb //ma[i]中存的是当前点 i 对应的一个点 //mb[i]中存的是当前点 i 对应的另一个点 cop(b, a);insert(a);//如果set中没有该元素,就插入,已经有了就删除,保证最后只剩下线段 起点 和 终点 insert(b); }int u = *q.begin();;//取出线段起点 q.clear();q.insert(u);printf("%d", u);while(n--){if(q.find(ma[u]) == q.end())u = ma[u];//如果 ma[u] 不在 q 中,更新 u // 如果ma[u] 在 q 中,说明对应的 ma[u] 已经遍历过,遍历mb[u]元素即可 else u = mb[u];q.insert(u);//把已经遍历过的点放入 q 中,方便下次判断 printf(" %d", u);}printf("\n");}return 0;
}
这篇关于Codeforces #29 C. Mail Stamps的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!